using namespace std; #include #include #include using Int=long long; int sign(Int a){return a>0?1:a<0?-1:0;} Int sqr(Int a){return a*a;} struct Rational{ Int a,b; Rational(Int a_=0):a(a_),b(1){} Rational(Int a_,Int b_){ Int g=a_,h=b_; while(h){ Int t=g%h; g=h; h=t; } a=a_/g; b=b_/g; if(b<0)a=-a,b=-b; } bool operator<(const Rational&r)const{return a*r.b>(istream&is,Point&p){return is>>p.x>>p.y;} ostream&operator<<(ostream&os,const Point&p){return os<; //function list begin Point vec(const Line&); Int norm(const Point&); Int norm(const Line&); int argtype(const Point&);//(-pi,0]->-1,(0,pi]->1,(0,0)->0 bool argless(const Point&,const Point&);//sorting points with arg Int dot(const Point&,const Point&); Int cross(const Point&,const Point&); enum{ONLINE_FRONT=-2,CLOCKWISE=-1,ON_SEGMENT=0,COUNTER_CLOCKWISE=1,ONLINE_BACK=2}; int ccw(const Point&,const Point&); int ccw(const Point&,const Point&,const Point&); int ccw(const Line&,const Point&); bool orthogonal(const Point&,const Point&); bool orthogonal(const Line&,const Line&); bool parallel(const Point&,const Point&); bool parallel(const Line&,const Line&); bool intersect(const Line&,const Point&); bool intersect(const Line&,const Line&); bool intersect(const Segment&,const Point&); bool intersect(const Segment&,const Segment&); bool intersect(const Line&,const Segment&); bool intersect(const Segment&,const Line&); bool intersect(const Circle&,const Point&); int intersect(const Circle&,const Line&);//overflow, count contacts int intersect(const Circle&,const Segment&);//overflow, count contacts bool intersect(const Circle&,const Circle&); int count_tangent(const Circle&,const Circle&);//count common tangents Int distance2(const Point&,const Point&); Rational distance2(const Line&,const Point&); Rational distance2(const Line&,const Line&); Rational distance2(const Segment&,const Point&); Rational distance2(const Segment&,const Segment&); Rational distance2(const Line&,const Segment&); Rational distance2(const Segment&,const Line&); bool is_convex(const Polygon&); Polygon convex_hull(Polygon,bool=false); enum{OUT,ON,IN}; int contain(const Polygon&,const Point&); int contain(const Circle&,const Point&); int contain(const Circle&,const Segment&); int convex_contain(const Polygon&,const Point&);//O(log |P|) Int diameter2(Polygon P); //function list end Point vec(const Line&s){return s.p2-s.p1;} Int norm(const Point&p){return p.x*p.x+p.y*p.y;} Int norm(const Line&s){return norm(vec(s));} int argtype(const Point&a){return a.y<0?-1:a.y>0?1:a.x<0?1:a.x>0?-1:0;} bool argless(const Point&a,const Point&b) { int at=argtype(a),bt=argtype(b); return at!=bt?at0; } Int dot(const Point&a,const Point&b){return a.x*b.x+a.y*b.y;} Int cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;} int ccw(const Point&a,const Point&b) { Int crs=cross(a,b); return crs>0?COUNTER_CLOCKWISE :crs<0?CLOCKWISE :dot(a,b)<0?ONLINE_BACK :norm(a)=sqr(c.r))||(d1>=sqr(c.r)&&d2=0&&dot(s.p1-s.p2,c.o-s.p2)>=0?t==1?1:2 :0; } bool intersect(const Circle&a,const Circle&b){ int c=count_tangent(a,b); return 1<=c&&c<=3; } int count_tangent(const Circle&a,const Circle&b){ Int d=distance2(a.o,b.o); return d==sqr(a.r+b.r)?3:d>sqr(a.r+b.r)?4:d==sqr(a.r-b.r)?1:d>sqr(a.r-b.r)?2:0; } Int distance2(const Point&a,const Point&b){return norm(a-b);} Rational distance2(const Line&s,const Point&p){ Int A=(s.p2.y-s.p1.y)*p.x+(s.p1.x-s.p2.x)*p.y-s.p1.x*s.p2.y+s.p1.y*s.p2.x; Int B=norm(s); return Rational(A*A,B); } Rational distance2(const Line&s,const Line&t){ return intersect(s,t)?Rational(0):distance2(s,t.p1); } Rational distance2(const Segment&s,const Point&p){ return dot(vec(s),p-s.p1)<0?Rational(distance2(p,s.p1)) :dot(-vec(s),p-s.p2)<0?Rational(distance2(p,s.p2)) :distance2(Line(s),p); } Rational distance2(const Segment&s,const Segment&t){ return intersect(s,t)?Rational(0):min({ distance2(s,t.p1),distance2(s,t.p2), distance2(t,s.p1),distance2(t,s.p2) }); } Rational distance2(const Line&s,const Segment&t){ return intersect(s,t)?Rational(0):min(distance2(s,t.p1),distance2(s,t.p2)); } Rational distance2(const Segment&s,const Line&t){return distance2(t,s);} bool is_convex(const Polygon&P){ for(int i=0;i=2&&ccw(ret[k-2],ret[k-1],p)==CLOCKWISE)k--; ret[k++]=p; } t=k; for(int i=P.size()-2;i>=0;i--){ while(k>=t+1&&ccw(ret[k-2],ret[k-1],P[i])==CLOCKWISE)k--; ret[k++]=P[i]; } } else{ for(const Point&p:P){ while(k>=2&&ccw(ret[k-2],ret[k-1],p)!=COUNTER_CLOCKWISE)k--; ret[k++]=p; } t=k; for(int i=P.size()-2;i>=0;i--){ while(k>=t+1&&ccw(ret[k-2],ret[k-1],P[i])!=COUNTER_CLOCKWISE)k--; ret[k++]=P[i]; } } ret.resize(k-1); int mi=0; for(int i=1;iret[i].x:ret[mi].y>ret[i].y)mi=i; rotate(ret.begin(),ret.begin()+mi,ret.end()); return ret; } int contain(const Polygon&P,const Point&p){ bool in=false; for(int i=0;ib.y)swap(a,b); if(a.y<=0&&00)in=!in; } } return in?IN:OUT; } int contain(const Circle&c,const Point&p){ Int d=distance2(c.o,p); return d==sqr(c.r)?ON:d1) { int mid=(l+r)/2; int t=ccw(P[0],P[mid],p); if(t==CLOCKWISE)r=mid; else l=mid; } if(r==1)return OUT; if(l+1==P.size()) { if(intersect(Segment(P[0],P[P.size()-1]),p))return ON; else return OUT; } if(l==1&&intersect(Segment(P[0],P[1]),p))return ON; Polygon tmp={P[0],P[l],P[l+1]}; int ret=contain(tmp,p); if(ret==ON) { if(intersect(Segment(P[l],P[l+1]),p))return ON; else return IN; } return ret; } Int diameter2(Polygon P){ if(!is_convex(P))P=convex_hull(P); int mi=0,Mi=0; for(int i=1;iP[Mi].x)Mi=i; } Int ret=0; int sm=mi,sM=Mi; while(mi!=sM||Mi!=sm){ ret=max(ret,norm(P[mi]-P[Mi])); if(cross(P[(mi+1)%P.size()]-P[mi],P[(Mi+1)%P.size()]-P[Mi])<0)mi=(mi+1)%P.size(); else Mi=(Mi+1)%P.size(); } return ret; } Int area2(Polygon P) { Int ret=0; for(int i=0;i int N; Int C[400][400]; Int dp[3][400]; int main() { cin>>N; Polygon PP(N); for(int i=0;i>PP[i]; Polygon P=convex_hull(PP); N=P.size(); if(N<4) { assert(N==3); Int ans=-1e18; for(int i=0;i=4); for(int i=0;i