Advertisement
Guest User

Untitled

a guest
Sep 25th, 2018
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement