World Final

World Final 1998 Crystal Clear

Posted in World Final on 十二月 2nd, 2010 by 纳米 – Be the first to comment

好久没更新了，继续更新吧。不过这次也该改目录名了，我也不是OIer了，要转型ACMer了。

题目大意：
以坐标系上每个整数坐标的点为圆心，直径为1建立圆。给定一个多边形，多边形上每条边的端点坐标都是整数。求被覆盖的圆的有效面积。
有效面积是这样定义的：
1. 如果整个圆都在多边形内，那么它的面积都是有效的；
2. 如果多边形的边穿过圆心，那么在多边形内的扇形面积是有效的。

解题方法：
因为坐标范围都很小，并且多边形的顶点都是整数，所以可以对于可能有效的圆，分别计算。对于每一个可能有效的圆：
1. 判断圆心是不是跟多边形某个顶点重合。如果是，累加扇形面积，结束；否则，转到2。
2. 判断圆心是否在某条边上。如果是，累加半圆面积，结束；否则，转到3.
3. 判断圆是否在多边形内。如果是，累加圆面积，结束。
圆在多边形内，当且仅当圆心离每一条边的距离不小于0.5，且圆心在多边形内。

几何知识（感谢gXX同学）：
以下用*表示叉积，@表示点积。
1. 叉积、点积、欧几里得距离。
2. 计算两向量夹角角度：利用余弦定理。
3. 点在线段上，点为p，线段端点p1、p2，v1、v2对应p到p1、p2的向量，下同：当且仅当v1 * v2 = 0，且v1 @ v2 < 0
4. 点到线段所在直线距离：d = |v1 * v2| / Distance(p1, p2)
5. 判断点在多边形内：射线法和转角法，参见《算法艺术与信息学竞赛》P381。代码用转角法实现。

注意事项：
用余弦定理和反三角函数只能算出锐角，但是扇形可能对应一个钝角。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

#include <cstdio>
#include <cmath>
 
const double pi = 3.1415926535897932384626433832795;
 
const int maxn = 27;
int n;
struct POINT {
	int x, y;
	POINT() {
		x = y = 0;
	}
	bool operator != (const POINT &value) {
		const POINT *that = &value;
		return this->x != that->x || this->y != that->y;
	}
	POINT operator -(const POINT &value) {
		const POINT *that = &value;
		POINT result;
		result.x = this->x - that->x;
		result.y = this->y - that->y;
		return result;
	}
} px[maxn];
 
bool input() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d%d", &px[i].x, &px[i].y);
	return (bool) n;
}
 
inline int min(int x, int y) {
	return x < y ? x : y;
}
 
inline int max(int x, int y) {
	return x > y ? x : y;
}
 
inline int CrossProduct(POINT v1, POINT v2) {
	return v1.x * v2.y - v2.x * v1.y;
}
 
inline int DotProduct(POINT v1, POINT v2) {
	return v1.x * v2.x + v1.y * v2.y;
}
 
inline double Distance(POINT p1, POINT p2) {
	return sqrt((double) ((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)));
}
 
inline double Angle(POINT p0, POINT p1, POINT p2) {
	POINT v0, v1, v2;
	v1 = p1 - p0;
	v2 = p2 - p0;
	return acos(DotProduct(v1, v2) / (Distance(v0, v1) * Distance(v0, v2)));
}
 
inline bool PointOnLine(POINT p, POINT p1, POINT p2) {
	POINT v1, v2;
	v1 = p1 - p;
	v2 = p2 - p;
	return !CrossProduct(v1, v2) && DotProduct(v1, v2) < 0;
}
 
inline double PointToLineDistance(POINT p, POINT p1, POINT p2) {
	POINT v1, v2;
	v1 = p1 - p;
	v2 = p2 - p;
	return fabs(CrossProduct(v1, v2) / Distance(p1, p2));
}
 
inline bool PointInPolygon(POINT p, POINT px[], int n) {
	// px[0] = px[n];
	double AngleSum = 0;
	for (int i = 1; i <= n; ++i) {
		int cp = CrossProduct(px[i - 1] - p, px[i] - p);
		if (cp > 0) {
			AngleSum += Angle(p, px[i - 1], px[i]);
		} else if (cp < 0) {
			AngleSum -= Angle(p, px[i - 1], px[i]);
		}
	}
	return fabs(AngleSum) > pi;
}
 
double solve() {
	double result = 0;
	POINT minp = px[1], maxp = px[1], p;
	for (int i = 2; i <= n; ++i) {
		minp.x = min(minp.x, px[i].x);
		minp.y = min(minp.y, px[i].y);
		maxp.x = max(maxp.x, px[i].x);
		maxp.y = max(maxp.y, px[i].y);
	}
	px[0] = px[n];
	px[n + 1] = px[1];
	for (p.x = minp.x; p.x <= maxp.x; ++p.x)
		for (p.y = minp.y; p.y <= maxp.y; ++p.y) {
			bool processed = false;
			if (!processed) {
				int k = 1;
				while (k <= n && px[k] != p)
					++k;
				if (k <= n) {
					if (CrossProduct(px[k] - px[k - 1], px[k + 1] - px[k]) < 0)
						result += Angle(px[k], px[k - 1], px[k + 1]) / 8;
					else
						result += (2 * pi - Angle(px[k], px[k - 1], px[k + 1])) / 8;
					processed = true;
				}
			}
			if (!processed) {
				int k = 1;
				while (k <= n && !PointOnLine(p, px[k - 1], px[k]))
					++k;
				if (k <= n) {
					result += pi / 8;
					processed = true;
				}
			}
			if (!processed) {
				bool broken = false;
				for (int i = 1; i <= n && !broken; ++i)
					broken = PointToLineDistance(p, px[i - 1], px[i]) < 0.5;
				if (!broken && PointInPolygon(p, px, n)) {
					result += pi / 4;
					processed = true;
				}
			}
		}
	return result;
}
 
int main() {
	int Cases = 0;
	while (input())
		printf("Shape %d\ninsulating area = %.3f cm^2\n", ++Cases, solve());
	return 0;
}