← 返回题目列表

AtCoder · xmascon18_f

F. 毛茸茸的狐狸

中文机器翻译题面 查看原题

配点: 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 长度 greater 的公共部分)。

制約

  • 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 个点用黄色表示,这是最大数量。