题目分析

题意简述

本题给定多组测试用例，每组测试用例包含蓝色插头的数量 $b$ 和红色插头的数量 $r$，以及每个蓝色插头和红色插头的坐标。需要判断是否可以通过某种方式将蓝色插头和红色插头分别连接成简单多边形，使得这两个多边形不相交。如果可以，输出 YES；否则，输出 NO。

输入

• 第一行输入一个整数 $t$，表示测试用例的数量。
• 对于每个测试用例：
  • 第一行输入两个整数 $b$ 和 $r$，分别表示蓝色插头和红色插头的数量。
  • 接下来的 $b$ 行，每行输入两个整数 $x$ 和 $y$，表示蓝色插头的坐标。
  • 再接下来的 $r$ 行，每行输入两个整数 $x$ 和 $y$，表示红色插头的坐标。

输出

对于每个测试用例，输出一行结果，YES 表示可以找到不相交的简单多边形，NO 表示找不到。

解题思路

凸包计算

首先，对蓝色插头和红色插头的坐标分别计算凸包。凸包是包含所有点的最小凸多边形，若两个凸包不相交，那么必然可以找到不相交的简单多边形连接这些点。

多边形相交判断

使用线段相交判断函数，检查两个凸包的所有边是否相交。若相交，则需要进一步检查是否存在其他不相交的简单多边形连接方式。

全排列枚举

若凸包相交，通过对蓝色插头和红色插头的坐标进行全排列，尝试所有可能的连接顺序，判断是否存在不相交的简单多边形。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Point {
    int x, y;
    bool operator<(const Point &p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};

// 2D cross product
int cross(const Point &O, const Point &A, const Point &B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

// Compute convex hull
vector<Point> convex_hull(vector<Point> P) {
    int n = P.size(), k = 0;
    if (n <= 3) return P;
    vector<Point> H(2 * n);

    sort(P.begin(), P.end());

    // Lower hull
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }

    // Upper hull
    for (int i = n - 2, t = k + 1; i >= 0; --i) {
        while (k >= t && cross(H[k - 2], H[k - 1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }

    H.resize(k - 1);
    return H;
}

// 判断点是否在线段上
bool onSegment(Point p, Point q, Point r) {
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
        return true;
    return false;
}

// 判断三个点的方向
int orientation(Point p, Point q, Point r) {
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;  // 共线
    return (val > 0)? 1 : 2; // 顺时针或逆时针
}

// 判断两条线段是否相交
bool doIntersect(Point p1, Point q1, Point p2, Point q2) {
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    if (o1 != o2 && o3 != o4) return true;

    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false;
}

// Check if two convex polygons intersect
bool polygons_intersect(const vector<Point>& poly1, const vector<Point>& poly2) {
    // 检查poly1的所有边与poly2的所有边是否相交
    for (int i = 0; i < static_cast<int>(poly1.size()); ++i) {
        for (int j = 0; j < static_cast<int>(poly2.size()); ++j) {
            Point p1 = poly1[i];
            Point q1 = poly1[(i + 1) % poly1.size()];
            Point p2 = poly2[j];
            Point q2 = poly2[(j + 1) % poly2.size()];

            if (doIntersect(p1, q1, p2, q2))
                return true;
        }
    }

    return false;
}

// 判断点是否在多边形内
bool pointInPolygon(Point p, const vector<Point>& poly) {
    int n = poly.size();
    if (n < 3) return false;

    bool inside = false;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        if ((poly[i].y > p.y) != (poly[j].y > p.y) &&
            p.x < (poly[j].x - poly[i].x) * (p.y - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x)
            inside = !inside;
    }
    return inside;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); // 使用NULL替代nullptr

    int t;
    cin >> t;
    while (t--) {
        int b, r;
        cin >> b >> r;
        vector<Point> blue(b), red(r);

        for (int i = 0; i < b; ++i)
            cin >> blue[i].x >> blue[i].y;
        for (int i = 0; i < r; ++i)
            cin >> red[i].x >> red[i].y;

        vector<Point> blue_hull = convex_hull(blue);
        vector<Point> red_hull = convex_hull(red);

        if (!polygons_intersect(blue_hull, red_hull)) {
            cout << "YES\n";
            continue;
        }

        // 如果凸包相交，进一步检查是否存在不相交的简单多边形
        bool possible = false;
        do {
            vector<Point> tempRed = red;
            do {
                // 构建蓝色多边形
                bool blueIntersect = false;
                for (int i = 0; i < b; ++i) {
                    Point p1 = blue[i];
                    Point q1 = blue[(i + 1) % b];
                    for (int j = 0; j < r; ++j) {
                        Point p2 = tempRed[j];
                        Point q2 = tempRed[(j + 1) % r];
                        if (doIntersect(p1, q1, p2, q2)) {
                            blueIntersect = true;
                            break;
                        }
                    }
                    if (blueIntersect) break;
                }
                if (!blueIntersect) {
                    possible = true;
                    break;
                }
            } while (next_permutation(tempRed.begin(), tempRed.end()));
            if (possible) break;
        } while (next_permutation(blue.begin(), blue.end()));

        if (possible) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}

代码说明

1. 点结构体

   • Point 结构体用于存储点的坐标，并重载了 < 运算符，用于排序。

2. 凸包计算

   • convex_hull 函数使用 Graham 扫描法计算点集的凸包。

3. 线段相交判断

   • onSegment 函数判断点是否在线段上。
   • orientation 函数判断三个点的方向。
   • doIntersect 函数判断两条线段是否相交。
   • polygons_intersect 函数检查两个多边形的所有边是否相交。

4. 点在多边形内判断

   • pointInPolygon 函数使用射线法判断点是否在多边形内。

5. 主函数

   • 读取输入的测试用例数量、蓝色插头和红色插头的数量及坐标。
   • 计算蓝色插头和红色插头的凸包。
   • 检查凸包是否相交，若不相交则输出 YES。
   • 若凸包相交，通过全排列枚举所有可能的连接顺序，判断是否存在不相交的简单多边形。
   • 根据判断结果输出 YES 或 NO。