洛谷 1355_神秘大三角_计算几何

发布于 2019-05-16  9 次阅读


题目描述

判断一个点与已知三角形的位置关系。


思路

可以知道如果这个点都在三条边的一侧(全部的m>0或全部的m<0),那它肯定是在三角形中
然后特殊判断一下4的情况,做的时候如果遇到m=0直接输出3
如果出现了变号的情况直接输出2,最后输出1即可


#include 
#include 
#include 
#include 
using namespace std;
inline int read(){
    int x=0,p=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
struct arr
{
    int x,y;
    void intput(){x=read();y=read();}
}edge[4];
arr r;
int find(arr a,arr b)
{
    return (b.x-r.x)*(a.y-r.y)-(a.x-r.x)*(b.y-r.y);
}
int find1(arr a,arr b,arr c)
{
    return min(a.x,b.x)<=c.x&&min(a.y,b.y)<=c.y&&max(a.x,b.x)>=c.x&&max(a.y,b.y)>=c.y;
}
int main()
{
    edge[1].intput(); edge[2].intput(); edge[3].intput();
    r.intput();
    int m=0,t=0;
    if (edge[1].x==r.x&&edge[1].y==r.y)
    {
        printf("4\n");
        return 0;
    }
    if (edge[2].x==r.x&&edge[2].y==r.y)
    {
        printf("4\n");
        return 0;
    }
    if (edge[3].x==r.x&&edge[3].y==r.y)
    {
        printf("4\n");
        return 0;
    }
    m=find(edge[1],edge[2]);
    if (m==0&&find1(edge[1],edge[2],r))
    {
        printf("3\n");
        return 0;
    }
    t=m;
    m=find(edge[2],edge[3]);
    if (m==0&&find1(edge[2],edge[3],r))
    {
        printf("3\n");
        return 0;
    }
    if (t>0&&m<0||t<0&&m>0)
    {
        printf("2\n");
        return 0;
    }
    t=m;
    m=find(edge[3],edge[1]);
    if (m==0&&find1(edge[3],edge[1],r))
    {
        printf("3\n");
        return 0;
    }
    if (t>0&&m<0||t<0&&m>0)
    {
        printf("2\n");
        return 0;
    }
    printf("1\n");

}

]]>