Codeforces 135 B. Rectangle and Square

Codeforces 幾何

問題

8つの点が与えられる。
それらを4つの点からなる共通しない集合2つに分ける。


そのうち一方が正方形の4頂点になっていて、もう一方が長方形の4頂点になっている（正方形でもよい）ような分け方は存在するか。


存在するならYESおよびその分け方を一通り出力し、そうでないならNOを出力せよ。
面積が0の図形は長方形または正方形とはみなさないものとする。

制約条件

座標の絶対値は10^4以下

方針

集合の分け方を全通り、集合のどの点がABCDのどの点に対応するかを全通り試す。


正方形、長方形の判定は、

  • ABベクトルがDCベクトルに等しい
  • ABベクトルを90度回転させるとADベクトルと平行になる
  • 正方形の場合、ABベクトルを90度回転させるとADベクトルに一致する

により行えばよい。

ソースコード

typedef complex<double> P;
vi X,Y;
bool ck(vi a,bool square){
	do{
		P p[4];
		rep(i,4)p[i]=P(X[a[i]],Y[a[i]]);
		rep(i,4)rep(j,i)if(abs(p[i]-p[j])<EPS)return 0;
		if(abs(p[1]-p[0]-(p[2]-p[3]))>EPS)continue;
		if(abs((p[1]-p[0])/abs(p[1]-p[0])-(p[3]-p[0])/abs(p[3]-p[0])*P(0,1))>EPS)continue;
		if(square&&abs(abs(p[1]-p[0])-abs(p[3]-p[0]))>EPS)continue;
		return 1;
	}while(next_permutation(all(a)));
	return 0;
}
void run()
{
	X.clear(); Y.clear();
	int x,y;
	rep(i,8){
		cin>>x>>y;
		X.pb(x); Y.pb(y);
	}
	rep(i,1<<8){
		vi a,b;
		rep(j,8)if(i&1<<j)a.pb(j); else b.pb(j);
		if(a.size()!=4)continue;
		if(ck(a,1)&&ck(b,0)){
			cout<<"YES"<<endl;
			rep(j,4)cout<<a[j]+1<<(j==3?"\n":" ");
			rep(j,4)cout<<b[j]+1<<(j==3?"\n":" ");
			goto END;
		}
	}
	cout<<"NO"<<endl; END:;
}