Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
うさぎは,友だちのきつねのためにクリスマスの飾り付けをしようとしている.きつねの耳の形 /\/\ をした模様を散りばめて,そのうえにたくさんの電球をつけたイルミネーションをつくろう.
問題文
xy 座標平面上の相異なる 5 つの格子点 (A, B, C, D, E) によって定まる 4 つの線分 (AB, BC, CD, DE) が /\/\ であるとは,\overrightarrow{AB} = \overrightarrow{CD} かつ \overrightarrow{BC} = \overrightarrow{DE} を満たすこととする.ここで,4 点 P(x_P, y_P), Q(x_Q, y_Q), R(x_R, y_R), S(x_S, y_S) に対し \overrightarrow{PQ} = \overrightarrow{RS} とは x_Q-x_P = x_S-x_R かつ y_Q-y_P = y_S-y_R が成り立つことを表す.
平面上に N 個の /\/\ を置き,2 本以上の線分 (端点を除く) の交点となっている点の個数を最大化せよ.このとき,以下の条件を満たす必要がある.
- 各 /\/\ を構成する 5 つの点は,すべてその x 座標および y 座標の絶対値が 10^9 以下の整数でなければならない.
- 各 /\/\ を構成する 5 つの点は,他の /\/\ を構成する点のいずれとも一致してはならない.
- 各 /\/\ によって定まる線分たちは,他のどの線分とも重なってはならない (すなわち,線分どうしが 0 より大きい長さの共通部分を持ってはならない).
制約
- 2 \le N \le 100.
入力
N
出力
x_{A_1} y_{A_1} x_{B_1} y_{B_1} x_{C_1} y_{C_1} x_{D_1} y_{D_1} x_{E_1} y_{E_1} x_{A_2} y_{A_2} x_{B_2} y_{B_2} x_{C_2} y_{C_2} x_{D_2} y_{D_2} x_{E_2} y_{E_2} \vdots x_{A_N} y_{A_N} x_{B_N} y_{B_N} x_{C_N} y_{C_N} x_{D_N} y_{D_N} x_{E_N} y_{E_N}
2 本以上の線分 (端点を除く) の交点となっている点の個数を最大化するような /\/\ の置き方を 1 つ出力せよ.
出力は N 行からなり,各行は 1 つの /\/\ を構成する 5 つの点 (A, B, C, D, E) の座標の情報をこの順に含む.それぞれの点は,x 座標および y 座標を表す 2 つの整数で表される (すなわち,A の x 座標,A の y 座標,B の x 座標,……といった順で出力する).
入力例 1
2
出力例 1
1 1 2 6 3 1 4 6 5 1 7 1 1 2 6 3 0 4 5 5
この出力例を図示すると以下のようになる.2 本以上の線分 (端点を除く) の交点となっている 16 個の点は黄色で表されており,これが最大個数である.