题解 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，不影响判定） ```cpp #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; } ```