yukicoder : No.2331 Maximum Quadrilateral

これは割とすんなり。
https://yukicoder.me/problems/no/2331

問題

2次元座標上でN点が与えられる。
4点を選び、作れる四角形の面積の最大値を求めよ。

解法

O(N^3)で解く。
対角に来る2点を総当たりしよう。
残り1点を総当たりするわけだが、その点が元の2点を結ぶ直線のどちら側にあるかで分類し、両側それぞれで面積が最大となる点を1点ずつ取ろう。
そうして選ぶ4点が解の候補となる。

最大面積の四角形が凹であっても、いずれかの対角線は四角形内にあるのでこの手順で漏れなくチェックできる。

int N;
int X[1010],Y[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll ret=0;
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(j,N) FOR(i,j) {
		ll ma=-1LL<<60,mi=1LL<<60;
		FOR(k,N) {
			if(k==i||k==j) continue;
			ll s=(X[i]-X[j])*(Y[k]-Y[j])-(Y[i]-Y[j])*(X[k]-X[j]);
			ma=max(ma,s);
			mi=min(mi,s);
		}
		ret=max(ret,ma-mi);
	}
	cout<<ret<<endl;
	
}

まとめ

コードも短くていいね。