QOJ.ac

QOJ

Límite de tiempo: 3 s Límite de memoria: 1024 MB Puntuación total: 100

#12142. 公平的水果蛋糕切分

Estadísticas

Frida 的生日快到了,作为她最好的朋友,你显然为她烤了一个蛋糕。因为你知道 Frida 喜欢旋转对称,所以你打算烤一个从上方看去旋转 $180^\circ$ 后形状不变的蛋糕。当然,你本可以烤一个普通的圆形蛋糕,但如果没有完美的圆形蛋糕模具,这说起来容易做起来难。因此,你决定烤一个形状由直线段描述的蛋糕。

图 F.1:样例输入 2 的可视化。这个看起来像 S 形的旋转蛋糕可以通过一次切割分成红色和蓝色两部分。

然而,在蛋糕烤好后,你发现你还想把蛋糕切成两等份,一份给 Frida,一份给自己。更准确地说,你想知道是否可以沿着一条无限长的直线切割蛋糕,使其正好分成两部分且重量相等。你可以假设蛋糕的密度和高度是均匀的。

输入格式

输入包含: 一行包含一个偶数 $n$ ($4 \le n \le 10^5$),表示描述蛋糕形状所需的点数。 $n$ 行,每行包含两个整数 $x, y$ ($0 \le x, y \le 10^6$),表示蛋糕形状边界上一个点的 $x$ 和 $y$ 坐标。

关于蛋糕形状的额外保证如下: 蛋糕具有 $180^\circ$ 旋转对称性。 点按逆时针顺序给出。 没有三个连续的点共线。 形状是简单的(没有线段相交,且只有相邻的线段在端点处接触)。

输出格式

输出目标直线上的两个不同点,格式为 $x_1/c_1 \ y_1/d_1 \ x_2/c_2 \ y_2/d_2$,其中 $|x_i|, |y_i|, |c_i|$ 和 $|d_i|$ 为整数且最大为 $10^9$,$x_i/c_i$ 是第 $i$ 个点的第一个坐标,$y_i/d_i$ 是第二个坐标 ($1 \le i \le 2$)。如果分母为 1,你可以只输出分子。分数不需要约分。如果没有这样的直线,则输出 “impossible”。

可以证明,如果存在所需的直线,则可以用给定的格式表示它。

样例

样例输入 1

4
0 0
2 0
2 2
0 2

样例输出 1

1 1 1337/42 3141/1000

样例输入 2

20
7 1
8 2
8 5
7 6
4 6
4 4
3 4
3 7
6 7
7 8
2 8
1 7
1 4
2 3
5 3
5 5
6 5
6 2
3 2
2 1

样例输出 2

11 13 -2 -4

样例输入 3

10
11 5
10 2
12 6
2 2
7 3
1 1
2 4
0 0
10 4
5 3

样例输出 3

impossible

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.