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
| #include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ls rt<<1
#define rs rt<<1|1
#define eps 1e-9
#define mod 998244353
#define MAXN 1e9
#define MS 1000009
#define M_PI acos(-1.0)
int n,m;
struct node{
double x,y;
}p[MS];
double lx,rx,ly,ry;
double get_angle(double x1, double y1, double x2, double y2, double x3, double y3) {
double theta = atan2(x1 - x3, y1 - y3) - atan2(x2 - x3, y2 - y3);
if (theta > M_PI)
theta -= M_PI*2;
if (theta < -M_PI)
theta += M_PI*2;
theta = abs(theta * 180.0 / M_PI);
return theta;
}
double calxy(double x, double y){
double minn = 180.0;
for(int i=1;i<=n;i++){
int t1 = i;
int t2 = (i==n)? 1:i+1;
double cc = get_angle(p[t1].x,p[t1].y,p[t2].x,p[t2].y,x,y);
minn = min(cc,minn);
}
return minn;
}
double cal(double x){
double L = ly, R = ry;
while(R-L>eps){
double M1 = (L*2+R)/3;
double M2 = (L+R*2)/3;
double T1 = calxy(x,M1);
double T2 = calxy(x,M2);
if(T1 < T2) L = M1;
else R = M2;
}
return calxy(x,R);
}
void solve(){
scanf("%d",&n);
lx = ly = MAXN;
rx = ry = -MAXN;
for(int i=1;i<=n;i++){
double x,y;
scanf("%lf %lf",&x,&y);
p[i] = {x,y};
lx = min(lx,x); rx = max(rx,x);
ly = min(ly,y); ry = max(ry,y);
}
double l = lx,r = rx;
while(r-l>eps){
double m1 = (l*2+r)/3;
double m2 = (l+r*2)/3;
double t1 = cal(m1);
double t2 = cal(m2);
if(t1 < t2) l = m1;
else r = m2;
}
double ans = cal(r);
printf("%.10lf\n",ans);
}
int main() {
int ce;
ce = 1;
while(ce--){
solve();
}
return 0;
}
|
