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