Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n;
- struct point{
- long long x,y;
- };
- point A[102];
- long long ccw(point a,point b,point c)
- {
- long long ans=0;
- ans+=(a.x-b.x)*(a.y+b.y);
- ans+=(b.x-c.x)*(b.y+c.y);
- ans+=(c.x-a.x)*(c.y+a.y);
- if (ans<0) return -1;
- if (ans==0) return 0;
- if (ans>0) return 1;
- }
- long long tich(point a,point b)
- {
- long long ans=(a.x-b.x)*(a.y+b.y);
- return ans;
- }
- int kt;
- int check(int l,int r)
- {
- for (int i=l+1;i<=r-1;i++)
- if (ccw(A[l],A[i],A[r])==0&&((A[l].x-A[i].x)*(A[r].x-A[i].x)<0||(A[l].y-A[i].y)*(A[r].y-A[i].y)<0)) return 0;
- for (int i=l+2;i<=r-1;i++)
- if (ccw(A[l],A[i-1],A[r])*ccw(A[l],A[i],A[r])<=0&&ccw(A[i-1],A[l],A[r])*ccw(A[i-1],A[r],A[i])<=0)
- return 0;
- return 1;
- }
- long long s=0;
- void solve()
- {
- cin>>n;
- for (int i=1;i<=n;i++)
- {
- cin>>A[i].x>>A[i].y;
- if (i>1) s+=tich(A[i-1],A[i]);
- }
- s+=tich(A[n],A[1]);
- if (s>0) kt=1;
- else kt=-1;
- long long res=1e18;
- for (int i=1;i<n;i++)
- {
- long long t=0;
- long long p=s;
- for (int j=i+1;j<=n;j++)
- {
- p-=tich(A[j-1],A[j]);
- t+=tich(A[j-1],A[j]);
- long long ss=t+tich(A[j],A[i]);
- long long pp=p+tich(A[i],A[j]);
- if (check(i,j)) res=min(res,abs(ss-pp));
- // cout<<i<<' '<<j<<' '<<t<<' '<<ss<<' '<<pp<<endl;
- }
- }
- double rr=double(res)/2;
- cout<<fixed<<setprecision(1)<<rr;
- }
- int main()
- {
- freopen("poly.inp","r",stdin);
- freopen("poly.out","w",stdout);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement