yicongli

LG4166

Mar 13th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define db double
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=2005;
  17.  
  18. struct Point{
  19.     db x,y;
  20.     inline bool operator < (const Point &a){return x==a.x?y<a.y:x<a.x;}
  21. };
  22. #define Vec Point
  23. inline Vec operator + (const Point &a,const Point &b){return Point{a.x+b.x,a.y+b.y};}
  24. inline Vec operator - (const Point &a,const Point &b){return Point{a.x-b.x,a.y-b.y};}
  25. inline db  operator * (const Point &a,const Point &b){return a.x*b.y-a.y*b.x;}
  26. inline db sqr(const db &a){return a*a;}
  27. inline db norm(const Vec &a){return sqr(a.x)+sqr(a.y);}
  28. inline bool cmp(const Vec &a,const Vec &b){
  29.     return (a*b>0)||(a*b==0&&norm(a)<norm(b));
  30. }
  31.  
  32. int sta[N],top;
  33. inline int convex(Point *A,int n){
  34.     Point tmp=A[1];
  35.     for(int i=2;i<=n;++i)if(A[i]<tmp)tmp=A[i];
  36.     for(int i=1;i<=n;++i)A[i]=A[i]-tmp;
  37.     sort(A+1,A+n+1,cmp);
  38.     sta[top=1]=1;
  39.     for(int i=2;i<=n;++i){
  40.         while(top>1&&(A[sta[top]]-A[sta[top-1]])*(A[i]-A[sta[top-1]])<=0)top--;
  41.         sta[++top]=i;
  42.     }
  43.     for(int i=1;i<=top;++i)A[i]=A[sta[i]]+tmp;
  44.     return top;
  45. }
  46.  
  47. inline db area(const Point &a,const Point &b,const Point &c){
  48.     return fabs((b-a)*(c-a));
  49. }
  50.  
  51. Point P[N];
  52.  
  53. int main(){
  54.     //freopen(".in","r",stdin);
  55.     //freopen(".out","w",stdout);
  56.     int n;scanf("%d",&n);
  57.     for(int i=1;i<=n;++i){
  58.         scanf("%lf%lf",&P[i].x,&P[i].y);
  59.     }
  60.     n=convex(P,n);
  61.     db ans=0;
  62.     for(int i=1;i<=n;++i){
  63.         int a=i%n+1;
  64.         int b=(i+2)%n+1;
  65.         for(int j=i+2;j<=n;++j){
  66.             while(a%n+1!=j&&area(P[i],P[j],P[a])<area(P[i],P[j],P[a%n+1]))a=a%n+1;
  67.             while(b%n+1!=i&&area(P[i],P[j],P[b])<area(P[i],P[j],P[b%n+1]))b=b%n+1;
  68.             ans=max(ans,area(P[i],P[j],P[a])+area(P[i],P[j],P[b]));
  69.         }
  70.     }
  71.     printf("%.3lf\n",ans/2);
  72. }
Add Comment
Please, Sign In to add comment