二维几何基础

1. 点、线、凸边形

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
/*******************************************************
二维几何基础
【注意】数组下标从1开始。
*******************************************************/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <string>
#define re register
#define il inline
#define ll long long
#define ld long double
using namespace std;
const ll MAXN = 1e5+5;
const ll INF = 1e9;
const ld EPS = 1e-9;

//点坐标
struct POINT
{
ld x, y;
POINT() : x(0), y(0) {}
POINT(ld _x, ld _y) : x(_x), y(_y) {}
};
//向量
typedef POINT VECTOR;

POINT xy[MAXN]; //顺时针多边形顶点存储
POINT xyB[MAXN]; //判断点存储


//符号函数
ll sgn(ld x) {return x < -EPS ? -1 : x > EPS;}
//向量+向量=向量,点+向量=点
VECTOR operator + (VECTOR a, VECTOR b) {return {a.x+b.x,a.y+b.y};}
//向量-向量=向量,点-点=向量
VECTOR operator - (VECTOR a, VECTOR b) {return {a.x-b.x,a.y-b.y};}
//向量*数=向量
VECTOR operator * (VECTOR a, ld k) {return {a.x*k,a.y*k};}
VECTOR operator * (ld k, VECTOR a) {return {a.x*k,a.y*k};}
//向量/数=向量
VECTOR operator / (VECTOR a, ld k) {return {a.x/k,a.y/k};}
//向量==向量,点==点
bool operator == (const VECTOR a, const VECTOR b) {return !sgn(a.x-b.x) && !sgn(a.y-b.y);}
//向量偏序关系(先x轴再y轴)
bool operator < (const VECTOR a, const VECTOR b) {return !sgn(a.x-b.x) ? a.y < b.y : a.x < b.x;}
//向量旋转(逆时针)
VECTOR rot(VECTOR a, ld sita) {return {a.x*cos(sita)-a.y*sin(sita),a.x*sin(sita)+a.y*cos(sita)};}
//取下端点
POINT min(POINT p1, POINT p2) {return p1.y<p2.y ? p1:p2;}
//取上端点
POINT max(POINT p1, POINT p2) {return p1.y<p2.y ? p2:p1;}
//点积
ld dot(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.x-p1.x)+(p.y-p1.y)*(p2.y-p1.y);} //(三点式:共p1端点)
ld dot(VECTOR a, VECTOR b) {return a.x*b.x+a.y*b.y;} //向量式
//叉积
ld cross(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.y-p1.y)-(p.y-p1.y)*(p2.x-p1.x);} //(三点式:共p1端点)
ld cross(VECTOR a, VECTOR b) {return a.x*b.y-a.y*b.x;} //向量式(aXb)
//向量长度
ld vlen(VECTOR a) {return sqrt(dot(a,a));}
//向量夹角余弦值
ld vcos(VECTOR a, VECTOR b) {return dot(a,b)/(vlen(a)*vlen(b));}
//向量夹角正弦值
ld vsin(VECTOR a, VECTOR b) {return fabs(cross(a,b))/(vlen(a)*vlen(b));}
//向量极角
ld vagl(VECTOR a, VECTOR b) {return acos(dot(a,b)/(vlen(a)*vlen(b)));} //向量间
ld vagl(VECTOR a) {return acos(a.x/vlen(a));}
//求直线斜率【注意】确保斜率存在
ld slope(VECTOR a) {return a.y/a.x;} //向量式
ld slope(POINT p, POINT q) {return (p.y-q.y)/(p.x-q.x);} //两点式
//单位向量【注意】确保非零向量
VECTOR unit(VECTOR a) {return a/vlen(a);}
//两直线交点
POINT intersectline(POINT p, VECTOR v, POINT q, VECTOR w) {return p+v*cross(w,p-q)/cross(v,w);} //(参数式:P=P0+t*v,P0为直线上某一点,v为直线的方向向量)
//点在直线上的投影
POINT proline(POINT a, POINT b, POINT p) {return a+(b-a)*(dot(b-a,p-a)/dot(b-a,b-a));}
//点关于直线的对称点
POINT refline(POINT a, POINT b, POINT p) {return proline(a,b,p)*2-p;}
//判断两直线是否平行
bool parallel(POINT p1, POINT p2, POINT q1, POINT q2) {return !sgn(cross(p2-p1,q2-q1)) && sgn(cross(p1-q1,p2-q1));}
//判断两直线重合
bool superposition(POINT p1, POINT p2, POINT q1, POINT q2) {return !sgn(cross(p2-p1,q2-q1)) && !sgn(cross(p1-q1,p2-q1));}
//点到直线距离
ld disline(POINT a, POINT b, POINT p) {return fabs(cross(b-a,p-a))/vlen(b-a);} //不取绝对值得到的是有向距离
//点到线段距离(两种情况:点的投影在线段上,则为垂直距离;点的投影不在线段上,则为到两端距离的最小值)
ld disseg(POINT a, POINT b, POINT p) {return a==b ? vlen(p-a):dot(b-a,p-a)<0 ? vlen(p-a):dot(b-a,p-b)>0 ? vlen(p-b):fabs(cross(b-a,p-a))/vlen(b-a);}
//线段相交判断(严格)
bool intersectseg(POINT p1, POINT p2, POINT q1, POINT q2) {return cross(p1-q1,q2-q1)*cross(p2-q1,q2-q1)<0 && cross(q1-p1,p2-p1)*cross(q2-p1,p2-p1)<0;}
//判断点p(x,y)是否在线段p1p2上(两种情况:1.包括端点;2.不包含端点)
bool onseg(POINT p1, POINT p2, POINT p) {return !sgn(cross(p1,p2,p)) && sgn(dot(p,p1,p2))<=0;} //包含端点
bool onseg_strict(POINT p1, POINT p2, POINT p) {return !sgn(cross(p1,p2,p)) && sgn(dot(p,p1,p2))<0;} //不包含端点

//点射法判断点是否在多边形内部(边界也算在内部)
//复杂度O(n)(不论凹凸)
bool inpolygon_dot(ld x, ld y, ll n)
{
ll cnt = 0;
for(re ll i = 0; i < n; ++i)
{
POINT p1 = min(xy[i+1], xy[(i+1)%n+1]); //取下端点
POINT p2 = max(xy[i+1], xy[(i+1)%n+1]); //取上端点
//特判点在线段上
if(onseg(p1,p2,{x,y})) return true;
//从点(x,y)向x反方向引出射线
//计算点射到的多边形的边数边数
if(sgn(p1.y-y)<0 && sgn(y-p2.y) <=0 && sgn(cross(p1,p2,{x,y}))>0) ++cnt;
}
if(cnt%2) return true;
else return false;
}

//二分法判断点是否在多边形内部(不包括边界)
//复杂度O(logn)(要求凸多边形)
bool inpolygon_bis(ld x, ld y, ll n)
{
POINT p = {x,y};
ll l = 2, r = n;
//判断是否在幅角最小和最大的两条边上
if(onseg(xy[1],xy[l],p) || onseg(xy[1],xy[n],p)) return false;
//二分法判断是否在多边形内部
while(l < r)
{
ll mid = (l+r)>>1; //【注意】如此取中点最终:r==l或r==l-1(只有此两种情况)
ll d = sgn(cross(xy[mid]-xy[1],p-xy[1]));
if(d < 0) l = mid+1;
else if(d > 0) r = mid-1;
else
{
if(onseg_strict(xy[1],xy[mid],p))
{
return true;
}
else
{
return false;
}
}
}
//判断在最终二分得到的对角线两端的边是否都满足严格在内的条件
if(l >= r && (sgn(cross(xy[l]-xy[l-1],p-xy[l-1]))>=0 || sgn(cross(xy[l%n+1]-xy[l],p-xy[l]))>=0))
{
return false;
}
return true;
}

//计算多边形面积(凹凸均可)
ld polygonarea(ll n)
{
ld aera = 0;
for(re ll i = 0; i < n; ++i)
{
aera += cross(xy[i+1], xy[(i+1)%n+1]);
}
//计算出来的aera为有向面积
return fabs(aera)/2;
}

int main()
{
std::ios::sync_with_stdio(false);
//判断直线平行/重合/相交
ll n;
cin >> n;
cout << "INTERSECTING LINES OUTPUT" << endl;
for(re ll i = 1; i <= n; ++i)
{
POINT p1, p2, p3, p4;
cin >> p1.x >> p1.y >> p2.x >> p2.y;
cin >> p3.x >> p3.y >> p4.x >> p4.y;
if(parallel(p1,p2,p3,p4)) cout << "NONE" << endl;
else if(superposition(p1,p2,p3,p4)) cout << "LINE" << endl;
else
{
POINT q = intersectline(p1,p2-p1,p3,p4-p3);
cout << "POINT " << fixed << setprecision(2) << q.x << " " << q.y << endl;
}
}
cout << "END OF OUTPUT" << endl;
return 0;
/*
//计算多边形的面积
ll n;
while(true)
{
std::cin >> n;
if(!n) break;
for(re ll i = 1; i <= n; ++i)
{
std::cin >> xy[i].x;
std::cin >> xy[i].y;
}
std::cout << std::fixed << std::setprecision(1) << polygonarea(n) << std::endl;
}
return 0;
*/
/*
//判断点是否在多边形内(不包括边界)
ll n;
std::cin >> n;
for(re ll i = 1; i <= n; ++i)
{
std::cin >> xy[i].x;
std::cin >> xy[i].y;
}
ll m;
cin >> m;
for(re ll i = 1; i <= m; ++i)
{
cin >> xyB[i].x;
cin >> xyB[i].y;
}
for(re ll i = 1; i <= m; ++i)
{
if(!inpolygon_bis(xyB[i].x, xyB[i].y, n))
{
printf("NO\n");
return 0;
}
}
printf("YES\n");
return 0;
*/
/*
//判断点是否在多边形内(包括边界)
ll N, M, k = 0;
while(!(std::cin >> N).eof())
{
if(!N) break;
std::cin >> M;
if(k) printf("\n");
++k;
for(re ll i = 1; i <= N; ++i)
{
std::cin >> xy[i].x;
std::cin >> xy[i].y;
//printf("(%f,%f)\n", xy[i].x, xy[i].y);
}
printf("Problem %lld:\n", k);
for(re ll i = 1; i <= M; ++i)
{
ld x, y;
std::cin >> x;
std::cin >> y;
//printf("(%f,%f)\n", x, y);
if(inpolygon(x, y, N))
{
printf("Within\n");
}
else
{
printf("Outside\n");
}
}
}
return 0;
*/
}

2. 圆

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
/*****************************************************************

【注意】三角与反三角最多用一次(损失精度大)。
*****************************************************************/

#include <bits/stdc++.h>
#include <iomanip>
#include <stack>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define re register
#define il inline
#define ll long long
#define ld long double
using namespace std;
const ld PI = 3.14159265358979323846;
const ll MAXN = 5e5+5;
const ld INF = 1e9;
const ld EPS = 1e-10;

//点坐标
struct POINT
{
ld x, y;
POINT() : x(0), y(0) {}
POINT(ld _x, ld _y) : x(_x), y(_y) {}
};
//向量
typedef POINT VECTOR;

//符号函数
ll sgn(ld x) {return x < -EPS ? -1 : x > EPS;}
//向量+向量=向量,点+向量=点
VECTOR operator + (VECTOR a, VECTOR b) {return {a.x+b.x,a.y+b.y};}
//向量-向量=向量,点-点=向量
VECTOR operator - (VECTOR a, VECTOR b) {return {a.x-b.x,a.y-b.y};}
//向量*数=向量
VECTOR operator * (VECTOR a, ld k) {return {a.x*k,a.y*k};}
VECTOR operator * (ld k, VECTOR a) {return {a.x*k,a.y*k};}
//向量/数=向量
VECTOR operator / (VECTOR a, ld k) {return {a.x/k,a.y/k};}
//向量==向量,点==点
bool operator == (const VECTOR a, const VECTOR b) {return !sgn(a.x-b.x) && !sgn(a.y-b.y);}
//向量偏序关系(先x轴再y轴)
bool operator < (const VECTOR a, const VECTOR b) {return !sgn(a.x-b.x) ? a.y < b.y : a.x < b.x;}
//取下端点
POINT min(POINT p1, POINT p2) {return p1.y<p2.y ? p1:p2;}
//取上端点
POINT max(POINT p1, POINT p2) {return p1.y<p2.y ? p2:p1;}
//点积
ld dot(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.x-p1.x)+(p.y-p1.y)*(p2.y-p1.y);} //(三点式:共p1端点)
ld dot(VECTOR a, VECTOR b) {return a.x*b.x+a.y*b.y;} //向量式
//叉积
ld cross(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.y-p1.y)-(p.y-p1.y)*(p2.x-p1.x);} //(三点式:共p1端点)
ld cross(VECTOR a, VECTOR b) {return a.x*b.y-a.y*b.x;} //向量式(aXb)
//向量长度
ld vlen(VECTOR a) {return sqrt(dot(a,a));}
//向量旋转(逆时针)
VECTOR rot(VECTOR a, ld sita) {return {a.x*cos(sita)-a.y*sin(sita),a.x*sin(sita)+a.y*cos(sita)};}
//取单位向量
VECTOR unit(VECTOR a) {return a/vlen(a);}
//取正交单位向量
VECTOR norm(VECTOR a) {return VECTOR(-a.y,a.x)/vlen(a);}
//向量夹角余弦值
ld vcos(VECTOR a, VECTOR b) {return dot(a,b)/(vlen(a)*vlen(b));}
//向量夹角正弦值
ld vsin(VECTOR a, VECTOR b) {return fabs(cross(a,b))/(vlen(a)*vlen(b));}
//向量极角
//【注意】使用系统反三角函数返回nan是因为超出了定义域(大多数由于精度造成)
//【注意】故使用系统反三角函数需处理边界
ld vagl(VECTOR a, VECTOR b)
{
ld d = dot(a,b)/(vlen(a)*vlen(b));
if(sgn(d-1) == 0) return 0;
else if(sgn(d+1) == 0) return PI;
else return acos(d);
} //向量间[0,PI]
ld vagl(VECTOR a) {return atan2(a.y, a.x);} //单向量[-PI,PI]

//直线
struct LINE
{
POINT p; //直线上定点
VECTOR v; //直线方向向量
LINE() {}
//点向式
LINE(POINT _p, VECTOR _v):p(_p), v(_v) {}
//点角式
LINE(POINT _p, ld a):p(_p), v(VECTOR(cos(a), sin(a))) {}
//通过参数t唯一确定直线上点坐标(点向式:P = p + t*v)
POINT point(ld t) {return p + t*v;}
//平移向量r
LINE trans(VECTOR r) {return LINE(p+r,v);}
};

//点到直线距离
ld PLdist(POINT p, LINE L) {return fabs(sin(vagl(p-L.p,L.v))*vlen(p-L.p));}

//圆
struct CIRCLE
{
POINT c; //圆心坐标
ld r; //半径
CIRCLE() {}
CIRCLE(POINT _c, ld _r):c(_c),r(_r) {}
//通过圆心角唯一确定圆上点坐标
POINT point(ld a) //a为圆心角
{
return POINT(c.x+cos(a)*r, c.y+sin(a)*r);
}
};

//两点中垂线
//返回中垂线的个数
ll PerpendicularBisector(POINT p1, POINT p2, LINE &L)
{
if(p1 == p2) return 0;
L.p = (p1+p2)/2;
L.v = rot(p2-p1, PI/2);
return 1;
}

//两直线交点
POINT LLitesct;

//直线与直线的交点
//返回交点个数
ll LineLineIntersection(LINE L1, LINE L2, POINT &p)
{
if(sgn(cross(L1.v, L2.v)) == 0)
{
if(sgn(cross(L2.p-L1.p,L2.v) == 0)) return -1; //两直线重合
else return 0; //两直线平行
}
//以L1为准
ld t1 = -cross(L2.p-L1.p, L2.v)/cross(L2.v, L1.v);
p = L1.p + t1*L1.v;
//以L2为准
//ld t2 = -cross(L1.p-L2.p, L1.v)/cross(L1.v, L2.v);
//p = L2.p + t2*L2.v;
return 1;
}

//直线与圆交点数组
vector <POINT> LCitesct;

//直线与圆的交点
//解方程:(at+b)^2+(ct+d)^2 = r^2;
//化简得:et^2+ft+g = 0
//返回交点个数
ll LineCircleIntersection(LINE L, CIRCLE C, ld &t1, ld &t2, vector <POINT>& sol)
{
ld a = L.v.x, b = L.p.x-C.c.x, c = L.v.y, d = L.p.y-C.c.y;
ld e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;
ld delta = f*f - 4*e*g;
if(sgn(delta) < 0) //相离
return 0;
else if(sgn(delta) == 0) //相切
{
t1 = t2 = -f/(2*e);
sol.push_back(L.point(t1));
return 1;
}
else
{
t1 = (-f - sqrt(delta))/(2*e);
t2 = (-f + sqrt(delta))/(2*e);
sol.push_back(L.point(t1));
sol.push_back(L.point(t2));
return 2;
}
}
ll LineCircleIntersection(LINE L, CIRCLE C, POINT *p)
{
ld t1, t2;
ld a = L.v.x, b = L.p.x-C.c.x, c = L.v.y, d = L.p.y-C.c.y;
ld e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;
ld delta = f*f - 4*e*g;
if(sgn(delta) < 0) //相离
return 0;
else if(sgn(delta) == 0) //相切
{
t1 = t2 = -f/(2*e);
p[0] = L.point(t1);
return 1;
}
else
{
t1 = (-f - sqrt(delta))/(2*e);
t2 = (-f + sqrt(delta))/(2*e);
p[0] = L.point(t1);
p[1] = L.point(t2);
return 2;
}
}

//圆与圆的交点数组
vector <POINT> CCitesct;

//两圆交点
ll CircleCircleIntersection(CIRCLE C1, CIRCLE C2, vector <POINT>& sol)
{
ld d = vlen(C1.c-C2.c);
if(sgn(d) == 0)
{
if(sgn(C1.r-C2.r) == 0) return -1; //两圆重合
else return 0; //同心相含
}
if(sgn(C1.r+C2.r-d) < 0) return 0; //相离
if(sgn(fabs(C1.r-C2.r)-d) > 0) return 0; //异心相含

//设两圆交点为p1,p2
ld a = vagl(C2.c - C1.c); //向量C1C2的极角
ld b = acos((C1.r*C1.r + d*d - C2.r*C2.r)/(2*C1.r*d)); //向量C1C2到C1P1(或C1P2)的夹角
POINT p1 = C1.point(a-b);
POINT p2 = C1.point(a+b);
sol.push_back(p1);
if(p1 == p2) return 1; //相切
sol.push_back(p2); //相交
return 2;
}

//圆切线方向向量
VECTOR LCtgt[2];

//过定点作圆的切线
ll Tangents(POINT p, CIRCLE C, VECTOR *v)
{
VECTOR u = C.c - p;
ld dist = vlen(u);
if(dist < C.r) return 0; //点在圆内,没有切线
else if(sgn(dist-C.r) == 0) //点在圆上,一条切线
{
v[0] = rot(u, PI/2);
return 1;
}
else //点在圆外,两条切线
{
ld a = asin(C.r/dist);
v[0] = rot(u, -a);
v[1] = rot(u, +a);
return 2;
}
}

//两圆公切点(分别在两圆上)
POINT CCtgt1[4], CCtgt2[4];

//两圆公切线
ll Tangents(CIRCLE C1, CIRCLE C2, POINT *a, POINT *b)
{
ll cnt = 0;
if(C1.r < C2.r) {swap(C1, C2); swap(a, b);}
ld d = dot(C1.c-C2.c, C1.c-C2.c);
ld rdiff = C1.r - C2.r;
ld rsum = C1.r + C2.r;
if(d < rdiff*rsum) return 0; //相含
ld base = atan2(C2.c.y-C1.c.y, C2.c.x-C1.c.x); //向量C1C2极角[-PI,PI]
if(sgn(d) == 0 && sgn(C1.r-C2.r) == 0) return -1; //重合
if(sgn(d-rdiff*rdiff) == 0) //内切
{
a[cnt] = C1.point(base);
b[cnt++] = C2.point(base);
return 1;
}
ld ang = acos((C1.r-C2.r)/sqrt(d)); //夹角[0,PI]
a[cnt] = C1.point(base+ang);
b[cnt++] = C2.point(base+ang);
a[cnt] = C1.point(base-ang);
b[cnt++] = C2.point(base-ang);
if(sgn(d-rsum*rsum)) //外切
{
a[cnt] = C1.point(base);
b[cnt++] = C2.point(base+PI);
}
else if(d > rsum*rsum) //相离
{
ld ang = acos((C1.r+C2.r)/sqrt(d));
a[cnt] = C1.point(base+ang);
b[cnt++] = C2.point(base+ang);
a[cnt] = C1.point(base-ang);
b[cnt++] = C2.point(base-ang);
}
return cnt; //切点个数
}

//三点外接圆
//返回外接圆的个数
ll CircumscribedCircle(POINT a, POINT b, POINT c, CIRCLE &C)
{
if(sgn(cross(a-b, b-c)) == 0) return 0; //三点共线
LINE L1, L2;
PerpendicularBisector(a, b, L1);
PerpendicularBisector(b, c, L2);
POINT p;
LineLineIntersection(L1, L2, p);
C.c = p;
C.r = vlen(p-a);
return 1;
}

//三点内接圆
//返回内接圆的个数
ll InscribedCircle(POINT a, POINT b, POINT c, CIRCLE &C)
{
if(sgn(cross(a-b, b-c)) == 0) return 0; //三点共线
LINE L1 = LINE(a, (vagl(b-a)+vagl(c-a))/2), L2 = LINE(b, (vagl(a-b)+vagl(c-b))/2);
POINT p;
LineLineIntersection(L1, L2, p);
C.c = p;
C.r = PLdist(p,LINE(a,b-a));
return 1;
}


int main()
{
//UVA-12304
//ios::sync_with_stdio(false);
string str;
while(cin >> str)
{
if(str == "CircumscribedCircle")
{
POINT a, b, c;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
CIRCLE C;
CircumscribedCircle(a,b,c,C);
cout << fixed << "(" << C.c.x << "," << C.c.y << "," << C.r << ")" << endl;
}
else if(str == "InscribedCircle")
{
POINT a, b, c;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
CIRCLE C;
InscribedCircle(a,b,c,C);
cout << fixed << "(" << C.c.x << "," << C.c.y << "," << C.r << ")" << endl;
}
//求已知圆的切线的极角
else if(str == "TangentLineThroughPoint")
{
CIRCLE C;
POINT p;
cin >> C.c.x >> C.c.y >> C.r >> p.x >> p.y;
VECTOR v[2];
ll cnt = Tangents(p,C,v);
cout << "[";
if(cnt == 1)
{
ld r = vagl(v[0]);
ld a = (sgn(r) < 0 ? PI+r : sgn(r-PI) == 0 ? 0 : r)*180/PI;
cout << fixed << a;
}
else if(cnt == 2)
{
ld mxr = vagl(v[0]);
ld mir = vagl(v[1]);
ld mxa = (sgn(mxr) < 0 ? PI+mxr : sgn(mxr-PI) == 0 ? 0 : mxr)*180/PI;
ld mia = (sgn(mir) < 0 ? PI+mir : sgn(mir-PI) == 0 ? 0 : mir)*180/PI;
if(mxa < mia) swap(mxa,mia);
cout << fixed << mia << "," << mxa;
}
cout << "]" << endl;
}
//求过定点且与已知直线相切的圆的圆心
else if(str == "CircleThroughAPointAndTangentToALineWithRadius")
{
CIRCLE P;
POINT p1, p2;
cin >> P.c.x >> P.c.y >> p1.x >> p1.y >> p2.x >> p2.y >> P.r;
VECTOR v = rot(p2-p1,PI/2);
ld t = P.r/vlen(v);
LINE L1 = LINE(p1+t*v,p2-p1), L2 = LINE(p1-t*v,p2-p1);
ll cnt = 0;
ld t1, t2;
vector <POINT> C;
cnt += LineCircleIntersection(L1,P,t1,t2,C);
cnt += LineCircleIntersection(L2,P,t1,t2,C);
sort(C.begin(),C.end());
cout << "[";
if(cnt == 1) cout << fixed << "(" << C[0].x << "," << C[0].y << ")";
else if(cnt == 2) cout << fixed << "(" << C[0].x << "," << C[0].y << ")" << "," << "(" << C[1].x << "," << C[1].y << ")";
cout << "]" << endl;
}
//求给定半径且与两条不相交直线相切的圆的圆心
else if(str == "CircleTangentToTwoLinesWithRadius")
{
POINT p1, p2, p3, p4;
ld r;
cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y >> p4.x >> p4.y >> r;
LINE L1 = LINE(p1,p2-p1), L2 = LINE(p3,p4-p3);
VECTOR v1 = norm(p2-p1), v2 = norm(p4-p3);
LINE L11 = L1.trans(r*v1), L12 = L1.trans(-r*v1);
LINE L21 = L2.trans(r*v2), L22 = L2.trans(-r*v2);
vector <POINT> C;
POINT p;
LineLineIntersection(L11,L21,p);
C.push_back(p);
LineLineIntersection(L11,L22,p);
C.push_back(p);
LineLineIntersection(L12,L21,p);
C.push_back(p);
LineLineIntersection(L12,L22,p);
C.push_back(p);
sort(C.begin(),C.end());
cout << "[";
cout << fixed << "(" << C[0].x << "," << C[0].y << ")" << "," << "(" << C[1].x << "," << C[1].y << ")" << ",";
cout << fixed << "(" << C[2].x << "," << C[2].y << ")" << "," << "(" << C[3].x << "," << C[3].y << ")";
cout << "]" << endl;

}
else if(str == "CircleTangentToTwoDisjointCirclesWithRadius")
{
CIRCLE C1, C2;
ld r;
cin >> C1.c.x >> C1.c.y >> C1.r >> C2.c.x >> C2.c.y >> C2.r >> r;
C1.r += r, C2.r += r;
vector <POINT> p;
ll cnt = CircleCircleIntersection(C1,C2,p);
sort(p.begin(),p.end());
cout << "[";
if(cnt == 1)
{
cout << fixed << "(" << p[0].x << "," << p[0].y << ")";
}
else if(cnt == 2)
{
cout << fixed << "(" << p[0].x << "," << p[0].y << ")" << "," << "(" << p[1].x << "," << p[1].y << ")";
}
cout << "]" << endl;
}
}
return 0;
}

3. 半平面

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
/*****************************************************************
半平面交
【注意】三角与反三角最多用一次(损失精度大)。
【注意】数组下标一律从1开始。
*****************************************************************/

//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <stack>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define re register
#define il inline
#define ll int
#define ld double
using namespace std;
const ld PI = 3.14159265358979323846;
const ll MAXN = 5e5+5;
const ld INF = 1e9;
const ld EPS = 1e-8;

//点坐标
struct POINT
{
ld x, y;
POINT() : x(0), y(0) {}
POINT(ld _x, ld _y) : x(_x), y(_y) {}
};
//向量
typedef POINT VECTOR;

//符号函数
ll sgn(ld x) {return x < -EPS ? -1 : x > EPS;}
//向量+向量=向量,点+向量=点
VECTOR operator + (VECTOR a, VECTOR b) {return {a.x+b.x,a.y+b.y};}
//向量-向量=向量,点-点=向量
VECTOR operator - (VECTOR a, VECTOR b) {return {a.x-b.x,a.y-b.y};}
//向量*数=向量
VECTOR operator * (VECTOR a, ld k) {return {a.x*k,a.y*k};}
VECTOR operator * (ld k, VECTOR a) {return {a.x*k,a.y*k};}
//向量/数=向量
VECTOR operator / (VECTOR a, ld k) {return {a.x/k,a.y/k};}
//向量==向量,点==点
bool operator == (const VECTOR a, const VECTOR b) {return !sgn(a.x-b.x) && !sgn(a.y-b.y);}
//向量偏序关系(先x轴再y轴)
bool operator < (const VECTOR a, const VECTOR b) {return !sgn(a.x-b.x) ? a.y < b.y : a.x < b.x;}
//取下端点
POINT min(POINT p1, POINT p2) {return p1.y<p2.y ? p1:p2;}
//取上端点
POINT max(POINT p1, POINT p2) {return p1.y<p2.y ? p2:p1;}
//点积
ld dot(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.x-p1.x)+(p.y-p1.y)*(p2.y-p1.y);} //(三点式:共p1端点)
ld dot(VECTOR a, VECTOR b) {return a.x*b.x+a.y*b.y;} //向量式
//叉积
ld cross(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.y-p1.y)-(p.y-p1.y)*(p2.x-p1.x);} //(三点式:共p1端点)
ld cross(VECTOR a, VECTOR b) {return a.x*b.y-a.y*b.x;} //向量式(aXb)
//向量长度
ld vlen(VECTOR a) {return sqrt(dot(a,a));}
//向量旋转(逆时针)
VECTOR rot(VECTOR a, ld sita) {return {a.x*cos(sita)-a.y*sin(sita),a.x*sin(sita)+a.y*cos(sita)};}
//取单位向量
VECTOR unit(VECTOR a) {return a/vlen(a);}
//取正交单位向量
VECTOR norm(VECTOR a) {return VECTOR(-a.y,a.x)/vlen(a);}
//向量夹角余弦值
ld vcos(VECTOR a, VECTOR b) {return dot(a,b)/(vlen(a)*vlen(b));}
//向量夹角正弦值
ld vsin(VECTOR a, VECTOR b) {return fabs(cross(a,b))/(vlen(a)*vlen(b));}
//向量极角
//【注意】使用系统反三角函数返回nan是因为超出了定义域(大多数由于精度造成)
//【注意】故使用系统反三角函数需处理边界
ld vagl(VECTOR a, VECTOR b)
{
ld d = dot(a,b)/(vlen(a)*vlen(b));
if(sgn(d-1) == 0) return 0;
else if(sgn(d+1) == 0) return PI;
else return acos(d);
} //向量间[0,PI]
ld vagl(VECTOR a) {return atan2(a.y, a.x);} //单向量[-PI,PI]

//凸包
ll vexcnt = 0; //凸包顶点数
POINT xy[MAXN], xyt[MAXN]; //多边形顶点存储,临时多边形顶点存储
POINT convex[MAXN]; //凸包顶点数组

//求凸包周长
ld convexperimeter(POINT *poly, ll n)
{
ld ans = 0;
for(re ll i = 1; i <= n; ++i)
{
ans += vlen(poly[i]-poly[i%n+1]);
}
return ans;
}
//计算多边形面积
ld polygonarea(POINT *poly, ll n)
{
ld aera = 0;
for(re ll i = 0; i < n; ++i)
{
aera += cross(poly[i+1], poly[(i+1)%n+1]);
}
return fabs(aera)/2; //不加绝对值为有向面积
}

//andrew算法求凸包(凸包数组正序为逆时针)
//1.严格凸包(没有重复点和三点共线)2.非严格凸包(允许重复点和三点共线)
void andrew(ll n)
{
vexcnt = 0; //初始化数据
memcpy(xyt,xy,sizeof(xy)); //备份原来顶点集
sort(xyt+1,xyt+n+1); //排序后xyt[1]和xyt[n]一定在凸包中
//求解凸包顶点集
//正向扫描(下凸包)
convex[++vexcnt] = xyt[1]; //xyt[1]一定在凸包中
ll j = 2;
while(j <= n)
{
if(vexcnt <= 1) //因为xyt[2]不一定在凸包集中
{
convex[++vexcnt] = xyt[j++];
}
else
{
//取前面两个点
//严格凸包:sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>0
//非严格凸包:sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>=0
if(sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>=0) convex[++vexcnt] = xyt[j++];
else --vexcnt;
}
}
//反向扫描(上凸包)
//至少包含了xyt[1]和xyt[n]
ll record = vexcnt; //记录下凸包的结果
ll k = n-1;
while(k >= 1)
{
if(vexcnt <= record)
{
convex[++vexcnt] = xyt[k--];
}
else
{
//取前面两个点
//严格凸包:sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[k]-convex[vexcnt]))>0
//非严格凸包:sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[k]-convex[vexcnt]))>=0
if(sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[k]-convex[vexcnt]))>0) convex[++vexcnt] = xyt[k--];
else --vexcnt;
}
}
while(convex[--vexcnt]==convex[1]); //因为和xyt[1]相等的点都在下凸包中了
//for(re ll i = 1; i <= vexcnt; ++i) cout << "(" << convex[i].x << "," << convex[i].y << ")" << endl;
return;
}

//直线
struct LINE
{
POINT p; //直线上定点
VECTOR v; //直线方向向量
LINE() {}
//点向式
LINE(POINT _p, VECTOR _v):p(_p), v(_v) {}
//点角式
LINE(POINT _p, ld a):p(_p), v(VECTOR(cos(a), sin(a))) {}
//通过参数t唯一确定直线上点坐标(点向式:P = p + t*v)
POINT point(ld t) {return p + t*v;}
//平移向量r
LINE trans(VECTOR r) {return LINE(p+r,v);}
};

//有向直线
struct DIRLINE
{
POINT p; //定点
VECTOR v; //方向向量
ld a; //极角
DIRLINE() {}
DIRLINE(POINT _p, VECTOR _v):p(_p),v(_v),a(atan2(v.y,v.x)) {}
bool operator < (const DIRLINE &DL) const {return a < DL.a;}
};

//点到直线距离
ld PLdist(POINT p, LINE L) {return fabs(sin(vagl(p-L.p,L.v))*vlen(p-L.p));}
//点在有向直线左边
bool OnLeft(DIRLINE DL, POINT p) {return sgn(cross(DL.v,p-DL.p)) > 0;}
//点在有向直线右边
bool OnRight(DIRLINE DL, POINT p) {return sgn(cross(DL.v,p-DL.p)) < 0;}

//两点中垂线
//返回中垂线的个数
ll PerpendicularBisector(POINT p1, POINT p2, LINE &L)
{
if(p1 == p2) return 0;
L.p = (p1+p2)/2;
L.v = rot(p2-p1, PI/2);
return 1;
}

//两直线交点
POINT LLitesct;

//直线与直线的交点
//返回交点个数
ll LineLineIntersection(LINE L1, LINE L2, POINT &p)
{
if(sgn(cross(L1.v, L2.v)) == 0)
{
if(sgn(cross(L2.p-L1.p,L2.v)) == 0) return -1; //两直线重合
else return 0; //两直线平行
}
//以L1为准
ld t1 = -cross(L2.p-L1.p, L2.v)/cross(L2.v, L1.v);
p = L1.p + t1*L1.v;
//以L2为准
//ld t2 = -cross(L1.p-L2.p, L1.v)/cross(L1.v, L2.v);
//p = L2.p + t2*L2.v;
return 1;
}
ll LineLineIntersection(DIRLINE DL1, DIRLINE DL2, POINT &p)
{
if(sgn(cross(DL1.v, DL2.v)) == 0)
{
if(sgn(cross(DL2.p-DL1.p,DL2.v)) == 0) return -1; //两直线重合
else return 0; //两直线平行
}
//以L1为准
ld t1 = -cross(DL2.p-DL1.p, DL2.v)/cross(DL2.v, DL1.v);
p = DL1.p + t1*DL1.v;
//以L2为准
//ld t2 = -cross(L1.p-L2.p, L1.v)/cross(L1.v, L2.v);
//p = L2.p + t2*L2.v;
return 1;
}

//半平面交
//返回凸包顶点数
//【注意】若半平面交可能是无界区域,则需在外面加一个坐标很大的包围框
ll HalfPlaneIntersection(DIRLINE *DL, ll n, POINT *poly)
{
sort(DL+1,DL+n+1);
ll first, last; //双端队列的首尾元素下标
DIRLINE *q = new DIRLINE[n+1]; //双端队列
POINT *p = new POINT[n+1]; //p[i]为q[i]和q[i+1]的交点
first = last = 1;
q[1] = DL[1]; //初始化只有一个半平面L[0]
for(re ll i = 2; i <= n; ++i)
{
while(first < last && !OnLeft(DL[i], p[last-1])) --last;
while(first < last && !OnLeft(DL[i], p[first])) ++first;
q[++last] = DL[i];
if(sgn(cross(q[last].v, q[last-1].v)) == 0) //两向量平行
{
--last;
if(OnLeft(q[last], DL[i].p)) q[last] = DL[i]; //同向取内测的一个
}
if(first < last) LineLineIntersection(q[last-1],q[last],p[last-1]);
}
while(first < last && !OnLeft(q[first],p[last-1])) --last;
//删除无用平面
if(last-first <= 1) return 0; //空集
LineLineIntersection(q[last],q[first],p[last]); //计算首尾两个半平面交的交点
ll cnt = 0;
for(re ll i = first; i <= last; ++i) poly[++cnt] = p[i];
return cnt;
}

int main()
{
//UVALive-3890
ios::sync_with_stdio(false);
ll n;
//scanf("%lld", &n);
while(cin >> n)
//while(~scanf("%d", &n))
{
if(n == 0) break;
POINT *p = new POINT[n+1];
for(re ll i = 1; i <= n; ++i)
{
cin >> p[i].x >> p[i].y;
//scanf("%lf%lf%lf%lf", &p1.x, &p1.y, &p2.x, &p2.y);
}
VECTOR *v = new VECTOR[n+1];
VECTOR *r = new VECTOR[n+1];
for(re ll i = 1; i <= n; ++i)
{
v[i] = p[i%n+1]-p[i];
r[i] = norm(v[i]); //单位正交向量
}
//二分答案
ld left = 0, right = 20000;
DIRLINE *DL = new DIRLINE[n+1];
POINT *poly = new POINT[n+1];
while(right-left > 1e-6)
{
ld mid = (left+right)/2;
for(re ll i = 1; i <= n; ++i)
{
DL[i] = DIRLINE(p[i]+r[i]*mid,v[i]);
}
ll cnt = HalfPlaneIntersection(DL,n,poly);
if(!cnt) right = mid;
else left = mid;
}
cout << fixed << setprecision(6) << left << endl;
}
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!