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;
} |
