zoj 1465 Wall

凸包后求各点为圆心的相邻圆的切线距离 以及某圆上两条切线交点之间的距离（如图的蓝色段 2条切线和一段弧长（2交点之间的弧长））

#include
#include
#include
#include
#include
#include
#define maxn 1001
#define INF 10000000
using namespace std;
int n;
double r;
struct node {
	double x, y;
} nds[maxn], q[maxn];
vector<node> v[maxn];
int l, per[maxn];
inline double getdis(node n1, node n2) {
	return (n2.x - n1.x) * (n2.x - n1.x) + (n2.y - n1.y) * (n2.y - n1.y);
}
inline node subs(node n1, node n2) {
	return node{n2.x - n1.x, n2.y - n1.y};
}
inline double mutix(node n1, node n2) {
	return n1.x * n2.y - n1.y * n2.x;
}
inline bool cmp(int p1, int p2) {
	int d = mutix(subs(nds[1], nds[p1]), subs(nds[1], nds[p2]));
	if (d != 0)return d > 0;
	return getdis(nds[1], nds[p1]) < getdis(nds[1], nds[p2]);
}
double getl() {
	double sum = 0, cosx, x;
	for (int i = 1; i <= l; i++) {
		cosx = (2 * r * r - getdis(v[i][0], v[i][1])) * 1.0 / (2 * r * r);
		x = acos(cosx);
		sum += x * r;
	}
	return sum;
}
void solve() {
	int i, id, cur;
	double D, sinx, cosx, sum, mx, my, dx, dy;
	id = 1;

	for (i = 2; i <= n; i++) {
		if (nds[i].x < nds[id].x || (nds[i].x == nds[id].x && nds[i].y < nds[id].y))id = i;
	}
	swap(nds[1], nds[id]);
	for (i = 1; i <= n; i++)per[i] = i;
	sort(per + 2, per + n + 1, cmp);
	l = 0;
	q[++l] = nds[1];
	for (i = 2; i <= n; i++) {
		cur = per[i];
		while (l >= 2 && mutix(subs(q[l - 1], q[l]), subs(q[l - 1], nds[cur])) <= 0)l--;
		q[++l] = nds[cur];
	}

	//计算圆的切线和切点
	for (i = 1; i <= l; i++) {
		v[i].clear();
	}
	sum = 0;
	for (i = 1; i <= l; i++) {
		dx = q[i % l + 1].x - q[i].x;
		dy = q[i % l + 1].y - q[i].y;
		D = sqrt(getdis(q[i % l + 1], q[i]));
		sum += D;
		if (dx == 0) {
			if (dy > 0) {
				v[i].push_back(node{q[i].x + r, q[i].y});
				v[i % l + 1].push_back(node{q[i % l + 1].x + r, q[i % l + 1].y});
			} else {
				v[i].push_back(node{q[i].x - r, q[i].y});
				v[i % l + 1].push_back(node{q[i % l + 1].x - r, q[i % l + 1].y});
			}
			continue;
		}
		if (dy == 0) {
			if (dx > 0) {
				v[i].push_back(node{q[i].x, q[i].y - r});
				v[i % l + 1].push_back(node{q[i % l + 1].x, q[i % l + 1].y - r});
			} else {
				v[i].push_back(node{q[i].x, q[i].y + r});
				v[i % l + 1].push_back(node{q[i % l + 1].x, q[i % l + 1].y + r});
			}
			continue;
		}
		sinx = abs(dx) / D;
		cosx = abs(dy) / D;
		mx = r * cosx;
		my = r * sinx;
		if (dx > 0) {
			if (dy < 0) {
				v[i].push_back(node{q[i].x - mx, q[i].y - my});
				v[i % l + 1].push_back(node{q[i % l + 1].x - mx, q[i % l + 1].y - my});
			} else {
				v[i].push_back(node{q[i].x + mx, q[i].y - my});
				v[i % l + 1].push_back(node{q[i % l + 1].x + mx, q[i % l + 1].y - my});
			}
		} else {
			if (dy < 0) {
				v[i].push_back(node{q[i].x - mx, q[i].y + my});
				v[i % l + 1].push_back(node{q[i % l + 1].x - mx, q[i % l + 1].y + my});
			} else {
				v[i].push_back(node{q[i].x + mx, q[i].y + my});
				v[i % l + 1].push_back(node{q[i % l + 1].x + mx, q[i % l + 1].y + my});
			}
		}
	}
	sum += getl();
	printf("%.0f\n", sum);
}

int main() {
	int T, i, x, y;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%lf", &n, &r);
		for (i = 1; i <= n; i++) {
			scanf("%d%d", &x, &y);
			nds[i].x = x;
			nds[i].y = y;
		}
		solve();
		if (T)printf("\n");
	}
}
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