题解 P1355 【神秘大三角】

发现先前写的题解存在bug

可以更正吗


楼下的面积法和叉积+重心好像都好高级

这里有直接用叉积做的

平面上的两点的直角坐标分别为p1(x1,y1),p2(x2,y2)则

叉积为m=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0)

若m>0 则相对p0点,点p1在点p2的顺时针方向

若m<0 则相对p0点,点p1在点p2的逆时针方向

若m=0 则p0和p1、p2在一条直线上

可以知道如果这个点都在三条边的一侧(全部的m>0或全部的m<0),那它肯定是在三角形中

然后特殊判断一下4的情况,做的时候如果遇到m=0直接输出3

如果出现了变号的情况直接输出2,最后输出1即可

写得很暴力,很长,但可能好理解

#include <stdio.h>
#include <string>
#include <cmath>
#include <iostream>
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");

}

发表于 2017-03-10 20:57:16 in 题解