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=2005;
- struct Point{
- db x,y;
- inline bool operator < (const Point &a){return x==a.x?y<a.y:x<a.x;}
- };
- #define Vec Point
- inline Vec operator + (const Point &a,const Point &b){return Point{a.x+b.x,a.y+b.y};}
- inline Vec operator - (const Point &a,const Point &b){return Point{a.x-b.x,a.y-b.y};}
- inline db operator * (const Point &a,const Point &b){return a.x*b.y-a.y*b.x;}
- inline db sqr(const db &a){return a*a;}
- inline db norm(const Vec &a){return sqr(a.x)+sqr(a.y);}
- inline bool cmp(const Vec &a,const Vec &b){
- return (a*b>0)||(a*b==0&&norm(a)<norm(b));
- }
- int sta[N],top;
- inline int convex(Point *A,int n){
- Point tmp=A[1];
- for(int i=2;i<=n;++i)if(A[i]<tmp)tmp=A[i];
- for(int i=1;i<=n;++i)A[i]=A[i]-tmp;
- sort(A+1,A+n+1,cmp);
- sta[top=1]=1;
- for(int i=2;i<=n;++i){
- while(top>1&&(A[sta[top]]-A[sta[top-1]])*(A[i]-A[sta[top-1]])<=0)top--;
- sta[++top]=i;
- }
- for(int i=1;i<=top;++i)A[i]=A[sta[i]]+tmp;
- return top;
- }
- inline db area(const Point &a,const Point &b,const Point &c){
- return fabs((b-a)*(c-a));
- }
- Point P[N];
- int main(){
- //freopen(".in","r",stdin);
- //freopen(".out","w",stdout);
- int n;scanf("%d",&n);
- for(int i=1;i<=n;++i){
- scanf("%lf%lf",&P[i].x,&P[i].y);
- }
- n=convex(P,n);
- db ans=0;
- for(int i=1;i<=n;++i){
- int a=i%n+1;
- int b=(i+2)%n+1;
- for(int j=i+2;j<=n;++j){
- 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;
- 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;
- ans=max(ans,area(P[i],P[j],P[a])+area(P[i],P[j],P[b]));
- }
- }
- printf("%.3lf\n",ans/2);
- }
Add Comment
Please, Sign In to add comment