daily pastebin goal
7%
SHARE
TWEET

Untitled

a guest Sep 25th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. struct point{
  5.     long long x,y;
  6. };
  7. point A[102];
  8. long long ccw(point a,point b,point c)
  9. {
  10.     long long ans=0;
  11.     ans+=(a.x-b.x)*(a.y+b.y);
  12.     ans+=(b.x-c.x)*(b.y+c.y);
  13.     ans+=(c.x-a.x)*(c.y+a.y);
  14.     if (ans<0) return -1;
  15.     if (ans==0) return 0;
  16.     if (ans>0) return 1;
  17. }
  18. long long tich(point a,point b)
  19. {
  20.     long long ans=(a.x-b.x)*(a.y+b.y);
  21.     return ans;
  22. }
  23. int kt;
  24. int check(int l,int r)
  25. {
  26.     for (int i=l+1;i<=r-1;i++)
  27.         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;
  28.     for (int i=l+2;i<=r-1;i++)
  29.         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)
  30.             return 0;
  31.     return 1;
  32. }
  33. long long s=0;
  34.  
  35. void solve()
  36. {
  37.     cin>>n;
  38.     for (int i=1;i<=n;i++)
  39.     {
  40.         cin>>A[i].x>>A[i].y;
  41.         if (i>1) s+=tich(A[i-1],A[i]);
  42.     }
  43.     s+=tich(A[n],A[1]);
  44.     if (s>0) kt=1;
  45.     else kt=-1;
  46.         long long res=1e18;
  47.     for (int i=1;i<n;i++)
  48.     {
  49.         long long t=0;
  50.         long long p=s;
  51.         for (int j=i+1;j<=n;j++)
  52.         {
  53.  
  54.             p-=tich(A[j-1],A[j]);
  55.             t+=tich(A[j-1],A[j]);
  56.             long long ss=t+tich(A[j],A[i]);
  57.             long long pp=p+tich(A[i],A[j]);
  58.             if (check(i,j)) res=min(res,abs(ss-pp));
  59.            // cout<<i<<' '<<j<<' '<<t<<' '<<ss<<' '<<pp<<endl;
  60.         }
  61.     }
  62.     double rr=double(res)/2;
  63.     cout<<fixed<<setprecision(1)<<rr;
  64. }
  65. int main()
  66. {
  67.     freopen("poly.inp","r",stdin);
  68.     freopen("poly.out","w",stdout);
  69.     solve();
  70. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top