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 <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n, cnt, tot;
const long double eps=1e-15;
struct Point{
long double x, y;
Point(long double u=0.0, long double v=0.0){
x = u; y = v;
}
Point operator+(const Point &u)const{
return Point(x+u.x, y+u.y);
}
Point operator-(const Point &u)const{
return Point(x-u.x, y-u.y);
}
long double crs(const Point &u)const{
return x*u.y-y*u.x;
}
}pt[100005], a[200005];
Point operator*(long double a, Point b){
return Point(a*b.x, a*b.y);
}
struct Line{
Point x, y;
long double ang;
Line(){}
Line(Point u, Point v){
x = u; y = v;
ang = atan2(v.y, v.x);
}
}l[200005], d[200005];
bool cmp(Line u, Line v){
if(fabs(u.ang-v.ang)>=eps) return u.ang<v.ang;
return u.y.crs(v.x+v.y-u.x)>eps;
}
Point inter(Line u, Line v){
Point a=u.x, b=a+u.y, c=v.x, d=c+v.y;
long double bil=(c-a).crs(d-a)/((c-a).crs(d-a)+(d-b).crs(c-b));
return a+bil*u.y;
}
bool isLeft(Point u, Line v){
return v.y.crs(u-v.x)>eps;
}
void halfPlaneIntersection(){
sort(l+1, l+1+cnt, cmp);
for(int i=1; i<=cnt; i++){
if(i==1 || fabs(l[i].ang-l[i-1].ang)>eps) tot++;
l[tot] = l[i];
}
cnt = tot; tot = 0;
int ll=1, rr=0;
d[++rr] = l[1]; d[++rr] = l[2];
for(int i=3; i<=cnt; i++){
while(ll<rr && !isLeft(inter(d[rr-1], d[rr]), l[i])) rr--;
while(ll<rr && !isLeft(inter(d[ll+1], d[ll]), l[i])) ll++;
d[++rr] = l[i];
}
while(ll<rr && !isLeft(inter(d[rr-1], d[rr]), d[ll])) rr--;
while(ll<rr && !isLeft(inter(d[ll+1], d[ll]), d[rr])) ll++;
d[rr+1] = d[ll];
for(int i=ll; i<=rr; i++)
a[tot++] = inter(d[i], d[i+1]);
}
long double getArea(Point a[], int n){
long double re=0;
if(n<3) return 0;
for(int i=0; i<n; i++)
re += a[i].crs(a[i+1]);
return re/2;
}
int main(){
cin>>n;
for(int i=0; i<n; i++)
scanf("%Lf %Lf", &pt[i].x, &pt[i].y);
pt[n] = pt[0];
for(int i=0; i<n; i++)
l[++cnt] = (Line){pt[i], pt[i+1]-pt[i]};
for(int i=1; i<n; i++){
long double A=pt[0].y-pt[1].y-pt[i].y+pt[i+1].y;
long double B=pt[1].x-pt[0].x-pt[i+1].x+pt[i].x;
long double C=-pt[1].x*pt[0].y+pt[0].x*pt[1].y+pt[i+1].x*pt[i].y-pt[i+1].y*pt[i].x;
Point o;
if(fabs(B)>=eps) o = Point(0.0, -C/B);
else o = Point(-C/A, 0.0);
l[++cnt] = Line(o, Point(-B, A));
}
halfPlaneIntersection();
a[tot] = a[0];
printf("%.4Lf\n", getArea(a, tot)/getArea(pt, n));
return 0;
}
|