UVa 11665 Chinese Ink

题目描述

$\text{Lucca}$ 是一个四岁的小女孩，她喜欢在绘图纸上画多边形。有一天，她画了几个多边形，并且用黑色的中国墨水将它们全部涂满。涂满之后，她想知道图中到底有多少个 黑色区域 。
一个黑色区域指的是纸上的一片黑色点集，其中任意两点都可以在该区域内用一条连续的黑色路径相连（即连通块）。
你的任务就是写一个程序，对于给定的若干个简单多边形（边界不自交），在将它们全部涂黑之后，统计图中黑色连通块的数量。

输入格式
输入包含多个测试用例。每个测试用例的格式如下：

• 第一行一个整数 $N$ （ $1\le N\le 40$ ），表示多边形的个数。
• 接下来 $N$ 行，每行描述一个多边形。每行包含 $2\cdot t$ 个整数 $x_1{y}_1{x}_2{y}_2\dots x_t{y}_t$ ，表示多边形边界上的顶点坐标（ $-10^4\le x_i,y_i\le 10^4$ ， $3\le t\le 10$ ）。多边形由这些顶点按顺序连接而成，最后一条边连接第 $t$ 个顶点和第一个顶点。题目保证多边形是简单多边形（边界不自交）。
• 输入以 $N=0$ 结束。

输出格式
对于每个测试用例，输出一行，表示将所有多边形涂黑后图中黑色区域的个数。

样例输入

5
35 29 179 111 19 145 183 22 305 22 305 80 183 80
232 49 361 49 361 178 232 178
137 94 188 156 112 164 79 144
129 143 129 193 79 193
2
20 20 30 20 30 30 20 30
40 40 40 50 50 50 50 40
2
20 20 30 20 30 30 20 30
30 30 40 30 40 40 30 40
3
20 20 40 20 40 40 20 40
50 30 60 20 70 50
60 40 50 30 30 50
0

样例输出

2
2
1
1

题目分析

问题本质

我们需要统计多个多边形在平面上被涂黑后，所有黑色区域形成的 连通块 数量。
关键点在于：

核心难点

如何判断两个多边形是否连通？
连通的定义是：两个多边形在平面上有公共的黑色区域。这发生在以下两种情况：

因此，我们需要实现两个几何判断：

• 线段相交判断（包括端点）。
• 点在多边形内部判断（射线法，包括点在边界上的情况）。

算法思路

复杂度分析

• 多边形数量 $N\le 40$ ，每个多边形的顶点数 $t\le 10$ 。
• 两两判断连通性需要 $O(N^2)$ 次判断，每次判断需要检查所有边对和顶点，最坏 $O(t^2)$ ，因此总复杂度 $O(N^2{t}^2)$ ，最大约为 $40^2\times 10^2=160000$ ，完全可行。

解题思路详解

1. 几何基础

叉积

给定三点 $P_0,P_1,P_2$ ，叉积 $cross(P_0,P_1,P_2)=(P_1-P_0)\times (P_2-P_0)$ ，可用于判断点 $P_2$ 在向量 $P_0{P}_1$ 的左侧还是右侧，以及判断三点共线。

线段相交判断

判断线段 $AB$ 和 $CD$ 是否相交（包括端点相交）：

点在多边形内部判断（射线法）

从点 $P$ 向右作水平射线，统计与多边形边相交的次数：

• 如果交点数为奇数，点在内部；
• 如果为偶数，点在外部。

注意边界情况：如果点 $P$ 在多边形的边上，直接返回在内部（因为涂黑后边界也是黑色）。

2. 并查集的使用

将所有多边形编号 $0$ 到 $N-1$ ，初始化每个多边形为一个集合。
每当发现两个多边形连通，就合并它们所在的集合。
最终，集合的数量就是连通块的数量。

3. 输入处理

每个多边形的输入是一行整数，个数为 $2t$ ，但 $t$ 没有显式给出，需要通过读取整数的个数来判断。
可以使用 while (cin >> val) 读取直到换行。

代码实现

// Chinese Ink
// UVa ID: 11665
// Verdict: Accepted
// Submission Date: 2026-01-14
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

struct Point {
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {}
};

typedef vector<Point> Polygon;

// 计算叉积 (p1-p0) × (p2-p0)
int cross(const Point& p0, const Point& p1, const Point& p2) {
return (p1.x – p0.x) * (p2.y – p0.y) – (p2.x – p0.x) * (p1.y – p0.y);
}

// 判断点是否在线段上（包括端点）
bool onSegment(const Point& p, const Point& a, const Point& b) {
if (min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y))
if (cross(p, a, b) == 0) return true;
return false;
}

// 判断线段 a-b 和 c-d 是否相交（包括端点）
bool segmentsIntersect(const Point& a, const Point& b, const Point& c, const Point& d) {
int d1 = cross(a, b, c);
int d2 = cross(a, b, d);
int d3 = cross(c, d, a);
int d4 = cross(c, d, b);
if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) return true;
if (d1 == 0 && onSegment(c, a, b)) return true;
if (d2 == 0 && onSegment(d, a, b)) return true;
if (d3 == 0 && onSegment(a, c, d)) return true;
if (d4 == 0 && onSegment(b, c, d)) return true;
return false;
}

// 射线法判断点是否在多边形内部（包括边界）
bool pointInPolygon(const Point& p, const Polygon& poly) {
int n = poly.size();
bool inside = false;
for (int i = 0; i < n; i++) {
Point a = poly[i], b = poly[(i + 1) % n];
if (onSegment(p, a, b)) return true; // 在边上
if ((a.y > p.y) != (b.y > p.y)) {
int intersectX = a.x + (p.y – a.y) * (b.x – a.x) / (b.y – a.y);
if (p.x < intersectX) inside = !inside;
}
}
return inside;
}

// 判断两个多边形是否相交或包含
bool polygonsIntersect(const Polygon& a, const Polygon& b) {
int na = a.size(), nb = b.size();
// 边相交检测
for (int i = 0; i < na; i++)
for (int j = 0; j < nb; j++)
if (segmentsIntersect(a[i], a[(i + 1) % na], b[j], b[(j + 1) % nb])) return true;
// 包含检测：a的顶点在b内，或b的顶点在a内
for (int i = 0; i < na; i++)
if (pointInPolygon(a[i], b)) return true;
for (int i = 0; i < nb; i++)
if (pointInPolygon(b[i], a)) return true;
return false;
}

// 并查集
class UnionFind {
public:
vector<int> parent;
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx != ry) parent[rx] = ry;
}
int countComponents() {
unordered_set<int> comps;
for (int i = 0; i < parent.size(); i++) comps.insert(find(i));
return comps.size();
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
while (cin >> n && n != 0) {
vector<Polygon> polygons(n);
for (int i = 0; i < n; i++) {
int t; vector<int> coords;
int val;
while (cin >> val) {
coords.push_back(val);
if (cin.peek() == '\\n') break;
}
t = coords.size() / 2;
for (int j = 0; j < t; j++) polygons[i].push_back(Point(coords[2 * j], coords[2 * j + 1]));
}
UnionFind uf(n);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (polygonsIntersect(polygons[i], polygons[j])) uf.unite(i, j);
cout << uf.countComponents() << "\\n";
}
return 0;
}

总结

本题是一道几何 + 并查集的综合题，关键在于正确判断两个多边形是否连通（相交或包含）。
实现时需要注意几何判断的细节，尤其是边界情况的处理（点在边上、端点相交等）。
使用并查集可以高效地合并连通的多边形，最终得到连通块的数量。
题目输入格式较为特殊，需要小心处理每行的顶点坐标读取。

通过本题，可以加深对几何算法和并查集应用的理解，同时锻炼处理复杂输入的能力。