Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define db double
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- const int N=2e5+7;
- const db eps=1e-10;
- inline int dcmp(const db &a){
- if(fabs(a)<eps)return 0;
- return a<0?-1:1;
- }
- struct Point{db x,y;};
- #define Vec Point
- inline Vec operator +(const Vec &a,const Vec &b){return Vec{a.x+b.x,a.y+b.y};}
- inline Vec operator -(const Vec &a,const Vec &b){return Vec{a.x-b.x,a.y-b.y};}
- inline Vec operator *(const Vec &a,const db &b){return Vec{a.x*b,a.y*b};}
- inline db operator *(const Vec &a,const Vec &b){return a.x*b.y-a.y*b.x;}
- inline db Angle(const Vec &a){return atan2(a.y,a.x);}
- struct Line{
- Point S;
- Vec V;
- db ang;
- inline Line (){}
- inline Line (const Point &s,const Point &v):S(s),V(v),ang(Angle(v)){}
- };
- inline bool operator < (const Line &a,const Line &b){
- double alpha=a.ang-b.ang;
- if(dcmp(alpha))return dcmp(alpha)==-1;
- return dcmp(a.V*(b.S-a.S))==-1;
- }
- inline Point cross(const Line &a,const Line &b){
- Vec u=a.S-b.S;
- db t=(u*b.V)/(b.V*a.V);
- return a.S+a.V*t;
- }
- inline bool OnRight(const Line &a,const Point &b){
- return dcmp((b-a.S)*a.V)==1;
- }
- int head,tail;
- Line Q[N];
- inline int Half(Line *A,int n,Point *B){
- sort(A+1,A+n+1);
- Q[head=tail=0]=A[1];
- for(int i=2;i<=n;++i){
- if(!dcmp(A[i].ang-A[i-1].ang))continue;
- while(head<tail&&OnRight(A[i],cross(Q[tail],Q[tail-1])))
- --tail;
- while(head<tail&&OnRight(A[i],cross(Q[head],Q[head+1])))
- ++head;
- Q[++tail]=A[i];
- }
- while(head<tail&&OnRight(Q[head],cross(Q[tail],Q[tail-1])))
- --tail;
- while(head<tail&&OnRight(Q[tail],cross(Q[head],Q[head+1])))
- ++head;
- int m=0;
- for(int i=head;i<tail;++i){
- B[m++]=cross(Q[i],Q[i+1]);
- }
- B[m++]=cross(Q[head],Q[tail]);
- return m;
- }
- Line L[N];
- Point P[N];
- int main(){
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- int n,tot=0;r(n);
- for(int i=0;i<n;++i){
- r(P[i].x),r(P[i].y);
- }
- db sum=0;
- for(int i=2;i<n;++i){
- sum+=(P[i-1]-P[0])*(P[i]-P[0]);
- }
- P[n]=P[0];
- for(int i=0;i<n;++i){
- L[++tot]=Line(P[i],P[i+1]-P[i]);
- }
- for(int i=1;i<n;++i){
- db a=P[0].y-P[1].y-P[i].y+P[i+1].y;
- db b=P[1].x-P[0].x+P[i].x-P[i+1].x;
- db c=P[0].x*P[1].y-P[0].y*P[1].x-P[i].x*P[i+1].y+P[i].y*P[i+1].x;
- if(dcmp(b))L[++tot]=Line(Point{0,-c/b},Vec{-b,a});
- else if(dcmp(a))L[++tot]=Line(Point{-c/a,0},Vec{-b,a});
- else if(c>0)return puts("0.0000"),0;
- }
- n=Half(L,tot,P);
- db ans=0;
- for(int i=2;i<n;++i){
- ans+=(P[i-1]-P[0])*(P[i]-P[0]);
- }
- printf("%.4lf",ans/sum);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement