これも地味にコーナーケースが多くいやらしい問題。
http://codeforces.com/contest/617/problem/D
問題
二次元座標上で異なる座標の3点が与えられる。
軸に平行な線分を連結してできるPolylineを作成し、これら3点を通るようにしたい。
必要な線分は最低何本か。
解法
丁寧に場合分けしていこう。
- X座標またはY座標がすべて同じなら1本。
- 2つの点のX座標が同じ場合、残り1点のY座標が、前者2つのY座標の間でなければ2本
- X座標が同じ点を結ぶ縦線を、残り1点のY座標まで伸ばせるため。
- 2つの点のY座標が同じ場合、残り1点のX座標が、前者2つのX座標の間でなければ2本
- それ以外は3本
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"); }
まとめ
通る点の順番が指定されてたら面倒そう。