UVA 10256 The Great Divide 解題：兩個凸包分離性判斷

題目大意

給定兩組點集，判斷其凸包是否相離 (無交點、無包含)。若相離輸出 "Yes"，否則 "No"。

演算法步驟

1. 分別計算兩組點的凸包 (CH1, CH2)，使用 Andrew 算法。
2. 判斷分離性：兩凸包相離當且僅當：
   • 無任何一點在另一凸包內部或邊界上 (點在多邊形判斷，射線法或叉積法)。
   • 無任何邊相交 (排除端點接觸，需真相交)。

幾何工具

struct Point { double x, y; };
double cross(Point a, Point b) { return a.x*b.y - a.y*b.x; }
Point operator-(Point a, Point b) { return {a.x-b.x, a.y-b.y}; }

bool onSegment(Point p, Point a, Point b) {
    return fabs(cross(a-p, b-p)) < eps && dot(a-p, b-p) < eps;
}
bool segIntersect(Point a1, Point a2, Point b1, Point b2) {
    double c1=cross(a2-a1,b1-a1), c2=cross(a2-a1,b2-a1);
    double c3=cross(b2-b1,a1-b1), c4=cross(b2-b1,a2-b1);
    return sgn(c1)*sgn(c2)<0 && sgn(c3)*sgn(c4)<0; // 真相交
}
int pointInPoly(Point p, vector& poly) {
    // 射線法，返回 0=外部, 1=內部, -1=邊界
}
bool disjoint(vector& ch1, vector& ch2) {
    for (auto p:ch1) if (pointInPoly(p,ch2)!=0) return false;
    for (auto p:ch2) if (pointInPoly(p,ch1)!=0) return false;
    for (int i=0;i