hiho一下第225周《Inside Triangle》题目分析

0
0

《Inside Triangle》题目分析

判断一个点是不是在一个多边形内是很经典的计算几何问题。一般可以是凸多边形也可以是凹多边形。

本题是这个经典问题的一个很简单的特例。

比较常用的算法是射线法，以要判断的点为起点任作一射线，计算该射线与多边形的交点数目。

若有偶数个交点则在形外，否则在形内。

若与线段在端点处相交或重合，则要进行复杂的判断。此时可另取一射线。

具体做法以及扩展，Point in Polygon Strategies 有很详细的讨论。

8 answer(s)

0

本来是wa的代码变ac了= =，是原本数据有问题么

0

使用海伦公式，控制精度在1e-5也能AC，但不推荐使用这种方法。

#include <bits/stdc++.h>
#define LL long double
using namespace std;

const double eps = 1e-5;
LL Heron(LL a, LL b, LL c)
{
    return 0.25 * sqrt((a + b + c) * (a + b - c) * (a + c - b) * (b + c - a));
}

LL Distance(LL x1, LL y1, LL x2, LL y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        LL x[4], y[4];
        for (int i = 0; i < 4; i++) cin >> x[i] >> y[i];
        LL s = 0;
        for (int i = 1; i <= 2; i++) {
            for (int j = i + 1; j < 4; j++) {
                LL a = Distance(x[0], y[0], x[i], y[i]), b = Distance(x[0], y[0], x[j], y[j]), c = Distance(x[i], y[i], x[j], y[j]);
                s += Heron(a, b, c);
            }
        }
        LL a = Distance(x[1], y[1], x[2], y[2]), b = Distance(x[1], y[1], x[3], y[3]), c = Distance(x[2], y[2], x[3], y[3]);
        //cout << s << ' ' << Heron(a, b, c) << endl;
        if (abs(s - Heron(a, b, c)) < eps) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}
1

三角形面积s=0.5*(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)); 只要省略每个面积的0.5，结果就是整数，没有精度问题

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL area(LL x1,LL y1,LL x2,LL y2,LL x3,LL y3)
{
    return abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
}

int main()
{
    LL Px, Py, Ax, Ay, Bx, By, Cx, Cy;
    LL S, S1, S2, S3;
    LL t;
    for(cin>>t;t>0;t--)
    {
        cin>>Px>>Py>>Ax>>Ay>>Bx>>By>>Cx>>Cy;
        S  = area(Ax, Ay, Bx, By, Cx, Cy);
        S1 = area(Px, Py, Ax, Ay, Bx, By);
        S2 = area(Px, Py, Ax, Ay, Cx, Cy);
        S3 = area(Px, Py, Bx, By, Cx, Cy);
        if(S1+S2+S3<=S)cout<<"YES\n";else cout<<"NO\n";
    }
    return 0;
}
1

面积法，误差控制在1e-5即可，已AC。

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
const double eps=0.00001;
double fun(double *a,double *b,double *c)
{
    double s=0.0;
    s=0.5*(a[0]*b[1]+b[0]*c[1]+c[0]*a[1]-a[0]*c[1]-b[0]*a[1]-c[0]*b[1]);
    return fabs(s);
}
int main()
{
    int i;
    scanf("%d",&i);
    while(i--)
    {
        double p[2]={0.0},x[2]={0.0},y[2]={0.0},z[2]={0.0};
        double area,areb,arec,ared;
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&p[0],&p[1],&x[0],&x[1],&y[0],&y[1],&z[0],&z[1]);
        area=fun(x,y,z);
        areb=fun(x,y,p);
        arec=fun(y,z,p);
        ared=fun(x,z,p);
        if(fabs(area-areb-arec-ared)<=eps)
        printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
1

可能是最简单的Java代码

import java.awt.Point;
import java.awt.geom.Point2D;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
double area(Point2D.Double a, Point2D.Double b, Point2D.Double c) {
    Point2D.Double one = new Point2D.Double(a.x - b.x, a.y - b.y), two = new Point2D.Double(a.x - c.x, a.y - c.y);
    double s = Math.abs(one.x * two.y - two.x * one.y) * 0.5;
    return s;
}

Main() {
    Scanner cin = new Scanner(System.in);
    int T = cin.nextInt();
    while (T-- > 0) {
        Point2D.Double p = new Point2D.Double(cin.nextDouble(), cin.nextDouble());
        Point2D.Double tri[] = new Point2D.Double[3];
        for (int i = 0; i < 3; i++) tri[i] = new Point2D.Double(cin.nextDouble(), cin.nextDouble());
        double s = area(tri[0], tri[1], tri[2]);
        double ss[] = new double[3];
        for (int i = 0; i < 3; i++) {
            ss[i] = area(p, tri[i], tri[(i + 1) % 3]);
        }
        double actual = Arrays.stream(ss).sum();
        if (Math.abs(actual - s) < 1e-5) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

public static void main(String[] args) {
    new Main();
}
}
0

还有个简单的方法，判断三条边的向量与P跟三个点连接的向量的叉积，如果三个叉积值同正负，则在三角形内。

  • 我也是用叉积的方法

  • 这么做的背后的理论基础是什么，有相关链接吗

  • 请问一下 我也用的这种方法 为什么会有30的样例是错的 是有一些情况要单独考虑吗

  • 我也是还有30的没过

  • @Kanon 30没过是因为用int溢出了，用long或者long long就全部AC

  • 添加评论
  • ✖reply
0

我的思路是这样: 要根据这个直角三角形补出一个矩形.直角三角形是矩形的一半,并且是位于是上三角形或者下三角形. 接下来:首先判断点是不是在矩形内,如果不在那肯定不在三角形里. 如果在则计算出三角形斜边对应的一次函数,计算点位于这条线的上部还是下部(位于线上属于在三角形内). 综合三角形是上三角形还是下三角形和点位于斜边上部还是下部得出点是否在三角形内. 下面是代码,给的例子能得到正确结果,提交之后WA,没想清楚错在哪. import java.util.Scanner;

class Point{ int x,y; public Point(int x,int y) { this.x = x; this.y = y; } }

class Main{

public void doTask() {
    Scanner scan = new Scanner(System.in);
    int testCases = scan.nextInt();
    Point[] points = new Point[3];
    while(testCases!=0) {
        Point p = new Point(scan.nextInt(),scan.nextInt());
        for(int i = 0; i < points.length;i++) {
            points[i] = new Point(scan.nextInt(),scan.nextInt());
        }
        boolean inTriangle = inTriangle(p,points);
        System.out.println(inTriangle? "YES":"NO");
        testCases--;
    }
    scan.close();
}


private boolean inTriangle(Point p, Point[] points) {
    //leftUp,rightUp,leftDown,rightDown
    Point[] sortedPoints = new Point[4];
    boolean inRectangle = inRectangle(p,points,sortedPoints);
    if(!inRectangle) {
        return false;
    }else {
        boolean res = help(p,sortedPoints);
        return res;
    }
}


private boolean help(Point p,Point[] sortedPoints) {
    boolean isTop = (sortedPoints[2]==null || sortedPoints[3]==null);
    Point[] edgePoints = getEdgePoint(sortedPoints);
    double k = (edgePoints[1].y-edgePoints[0].y)*1.0/(edgePoints[1].x-edgePoints[0].x);
    double b = edgePoints[1].y - k * edgePoints[1].x;
    double sample = k * p.x + b;
    if(p.y==sample) {
        return true;
    }
    boolean topOfLine = (p.y > sample);
    return topOfLine==isTop;
}


private Point[] getEdgePoint(Point[] sortedPoints) {
    for(int i = 0; i < sortedPoints.length;i++) {
        for(int j = 0; j < sortedPoints.length;j++) {
            if(sortedPoints[i]==null || sortedPoints[j]==null) {
                continue;
            }else {
                if(sortedPoints[i].x != sortedPoints[j].x && sortedPoints[i].y != sortedPoints[j].y) {
                    Point[] points = {sortedPoints[i],sortedPoints[j]};
                    return points;
                }
            }
        }
    }
    return null;
}


private boolean inRectangle(Point p, Point[] points, Point[] sortedPoints) {
    int minX = points[0].x;
    int maxX = points[0].x;
    int minY = points[0].y;
    int maxY = points[0].y;
    for(Point point:points) {
        minX = Math.min(minX, point.x);
        maxX = Math.max(maxX, point.x);
        minY = Math.min(minY, point.y);
        maxY = Math.max(maxY, point.y);
    }
    if(p.x<minX||p.y<minY||p.x>maxX||p.y>maxY) {
        return false;
    }else {
        sortedPoints[0] = new Point(minX,maxY);
        sortedPoints[1] = new Point(maxX,maxY);
        sortedPoints[2] = new Point(minX,minY);
        sortedPoints[3] = new Point(maxX,minY);
        //找却失的那个
        int remain = getRemain(sortedPoints,points);
        sortedPoints[remain] = null;
        return true;
    }
}


private int getRemain(Point[] sortedPoints, Point[] points) {
    for(int i = 0; i < sortedPoints.length;i++) {
        if(!contains(points,sortedPoints[i])) {
            return i;
        }
    }
    return -1;
}


private boolean contains(Point[] points, Point target) {
    for(Point point:points) {
        if(point.x==target.x && point.y==target.y) {
            return true;
        }
    }
    return false;
}


public static void main(String[] args) {
    Main m = new Main();
    m.doTask();
}

}

0

用面积法应该更简单，如果是点p和ABC三点分别组成的三角形的面积和等于三角形ABC的面积，这样就在里面，否则在外面

  • 面积的精度怎么保证啊

  • 因为输入的点都是整数所以三角形的面积肯定都是有理数（可以通过叉积计算平行四边形的面积），然后就是浮点数判断相等

  • 输入的都是整数，三角形面积计算s=0.5*(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)); 所有面积里都有这个0.5，去掉这个0.5对结果不影响，于是面积计算出来就是整数，没有精度问题了

  • 厉害呀，好像是这么回事，面积在除以2之前确实是个整数 之前面积上一直考虑的是海伦公式，刚才画了两笔，把格子画出来看了看就明白了，thanks

  • 添加评论
  • ✖reply

write answer 切换为英文 切换为中文

转发分享

▲