POJ-2079 : Triangle

問題概要

2次元平面上にN(<10^5)個の点(|x|,|y|<10^4, 座標は整数)がある。3点選んで作ることのできる三角形の面積を最大化せよ。

解法

まず凸包を作る。整数座標なので凸包は100個ちょいしか残らない。N^3だとTLEするのでキャリパーっぽくN^2でやる。底辺の2点の組み合わせを全探索する。もっと速く解けるらしい。

acceptされたコード

int N;
vector<Point> ps;

bool init(){
	scanf("%d", &N);

	ps.clear();
	for(int i=0; i<N; ++i){
		long long x, y;
		scanf("%lld%lld", &x, &y);
		ps.push_back(Point(x,y));
	}

	return N != -1;
}

real solve(){
	ps = convex_hull(ps);
	N = ps.size();
	real ans = 0;

	for(int len=1; len < N; ++len){
		int p = (len+1)%N;
		for(int i=0; i<N; ++i){
			int nxt = (i+len)%N	;
			real prev = det(ps[i], ps[nxt], ps[p]);
			if(prev < 0) prev = -prev;
			for(++p;p!=nxt && p!=i;++p){
				if(p == N) p = 0;
				real cur = det(ps[i], ps[nxt], ps[p]);
				if(cur < 0) cur = -cur;
				ans = max(ans, prev);
				if(cur <= prev){
					break;
				}
				prev = cur;
			}
			--p;
			if(p == -1) p += N;
		}
	}

	return ans;
}

int main(){
	for(;init();){
		real ans = solve();
		printf("%lld.%s\n", ans/2, ans%2==1?"50":"00");
	}

	return 0;
}