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);
	}
}