PKU 2079-Triangle
問題概要
N個の点が与えられる。この中で3つの点を選んで三角形を作った時の面積の最大値を求めよ。
解法
座標の範囲が小さいので凸包を取ることで大幅に点が減る。
後は任意の二点に対して、最後の点を3分探索する。
実装(C++)
vector<Point> pts; int x[50000],y[50000]; int area(int i,int j,int k){ int x1=x[k]-x[i]; int x2=x[j]-x[i]; int y1=y[k]-y[i]; int y2=y[j]-y[i]; return abs(x1*y2-x2*y1); } int main(){ while(true){ int n; scanf("%d",&n); if(n<0)break; pts=vector<Point>(n); for(int i=0;i<n;i++){ scanf("%lf%lf",&pts[i].real(),&pts[i].imag()); } pts=convex_hull(pts); n=pts.size(); int ans=0; for(int i=0;i<n;i++){ x[i]=pts[i].real(); y[i]=pts[i].imag(); } for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ int low=j+1,high=n; if(low>=n)break; for(int k=0;k<30;k++){ int m1=low+(high-low)/3; int m2=low+(high-low)*2/3; int a1=area(i,j,m1); int a2=area(i,j,m2); if(a1>a2){ high=m2; }else{ low=m1; } ans=max(ans,a1); if(m2<n)ans=max(ans,a2); } } } printf("%.02f\n",ans*.5); } }