题解 P1355 【神秘大三角】
题解

基础计算几何,可以练习一下叉积

对于△ABC和点P

判点在点上:直接判相等就是了。

判点在边上:向量AB×向量BP=0,且x_p∈[min(x_a,x_b),max(x_a,x_b)],y同理,则P在AB上

判点在三角形内:先得出三角形重心H,横纵坐标为ABC的平均值,一定在三角形内。若P和H在AB,BC,AC同侧,则P在三角形内。若向量AB×向量BP与向量AB×向量BH同号,则H,P在AB同侧。

其它情况就是在三角形外了。

代码如下(防止重心坐标不能被整除,把输入的坐标都乘上3,不影响判定)


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int iRead()
{
    int ret = 0, ch;
    while(!isdigit(ch = getchar()) && ch != '-');
    bool bm = (ch == '-'); if(bm) ch = getchar();
    while(ret = ret * 10 + (ch - '0'), isdigit(ch = getchar()));
    return bm ? -ret : ret;
}

struct iP
{
    int x, y;
    bool operator==(const iP &r) const {return x == r.x && y == r.y;}
    iP operator-(const iP &r) const {return (iP){x - r.x, y - r.y};}
}a, b, c, p;

int iCross(const iP &a, const iP &b)
{
    return a.x * b.y - a.y * b.x;
}

bool iInl(const iP &p, const iP &l, const iP &r)
{
    return 
        p.x >= min(l.x, r.x) && p.x <= max(l.x, r.x) &&
        p.y >= min(l.y, r.y) && p.y <= max(l.y, r.y) &&
        iCross(r - l, p - r) == 0;
}

bool iSame(const iP &p, const iP &q, const iP &l, const iP &r)
{
    return (iCross(r - l, p - r) ^ iCross(r - l, q - r)) >= 0;
}

int main()
{
    a.x = iRead() * 3, a.y = iRead() * 3;
    b.x = iRead() * 3, b.y = iRead() * 3;
    c.x = iRead() * 3, c.y = iRead() * 3;
    p.x = iRead() * 3, p.y = iRead() * 3;
    iP h = {(a.x + b.x + c.x) / 3, (a.y + b.y + c.y) / 3};

    if(p == a || p == b || p == c)
        puts("4");
    else if(iInl(p, a, b) || iInl(p, b, c) || iInl(p, c, a))
        puts("3");
    else if(iSame(p, h, a, b) && iSame(p, h, b, c) && iSame(p, h, c, a))
        puts("1");
    else
        puts("2");

    return 0;
}
评论