Codeforces #340 Div2. D. Polyline

これも地味にコーナーケースが多くいやらしい問題。
http://codeforces.com/contest/617/problem/D

問題

二次元座標上で異なる座標の３点が与えられる。
軸に平行な線分を連結してできるPolylineを作成し、これら３点を通るようにしたい。

必要な線分は最低何本か。

解法

丁寧に場合分けしていこう。

• X座標またはY座標がすべて同じなら1本。
• 2つの点のX座標が同じ場合、残り1点のY座標が、前者2つのY座標の間でなければ2本
  • X座標が同じ点を結ぶ縦線を、残り1点のY座標まで伸ばせるため。
• 2つの点のY座標が同じ場合、残り1点のX座標が、前者2つのX座標の間でなければ2本
• それ以外は３本

ll X[3],Y[3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,3) cin>>X[i]>>Y[i];
	if(X[0]==X[1]&&X[1]==X[2]) return _P("1\n");
	if(Y[0]==Y[1]&&Y[1]==Y[2]) return _P("1\n");
	FOR(i,3) FOR(j,3) FOR(k,3) if(i!=j&&j!=k&&i!=k) {
		if(X[i]==X[j] && (Y[k]<=min(Y[i],Y[j])||max(Y[i],Y[j])<=Y[k])) return _P("2\n");
		if(Y[i]==Y[j] && (X[k]<=min(X[i],X[j])||max(X[i],X[j])<=X[k])) return _P("2\n");
	}
	_P("3\n");
}

まとめ

通る点の順番が指定されてたら面倒そう。