QOJ.ac

QOJ

実行時間制限: 2.0 s メモリ制限: 512 MB 満点: 100

#16963. 新公寓

統計

Flato 住在 Flatland 的首都 Flatburg,他刚刚买了一套新公寓!他唯一的问题是,搬家工人在搬进他最喜欢的沙发时,把它放错了地方。现在 Flato 想通过移动沙发来解决这个问题,但沙发相当长。你能帮帮 Flato 吗?

与 Flatland 的所有公寓一样,Flato 的公寓是一个凸多边形。他最喜欢的沙发无限薄,因此我们将其表示为一条线段。正式地讲,我们有一个表示公寓的多边形 $P$ 和一个表示沙发的在多边形内部的线段 $AB$。如果存在两个从 $[0, 1]$ 到 $P$ 的内部或边界的连续函数 $f$ 和 $g$,满足 $f(0) = A$,$f(1) = C$,$g(0) = B$,$g(1) = D$,且对于所有的 $0 \le x \le 1$ 都有 $|f(x)g(x)| = |AB|$,我们就说沙发可以到达位置 $CD$。你的任务是求出在所有可到达的位置 $CD$ 中,直线 $AB$ 和 $CD$ 之间夹角的最大可能值。两条直线之间的夹角定义为它们交点处两个夹角中的较小者,如果两条直线平行,则夹角为 0。

输入格式

输入的第一行包含五个整数 $n, x_A, y_A, x_B$ 和 $y_B$($3 \le n \le 50$;$-15\,000 \le x_A, y_A, x_B, y_B \le 15\,000$)—— $P$ 的顶点数以及沙发两端的坐标。

接下来的 $n$ 行,每行包含两个整数 $x$ 和 $y$($-15\,000 \le x, y \le 15\,000$)—— 按逆时针顺序给出的多边形顶点的坐标。

保证 $A$ 和 $B$ 均在 $P$ 的内部或边界上,且多边形是凸的。

输出格式

输出如题目描述中所述的最大夹角(以度为单位)。如果你的输出的绝对或相对误差不超过 $10^{-6}$,则将被视为正确。

样例

输入样例 1

6 2 1 -2 1
2 1
0 3
-2 1
-2 -1
0 -3
2 -1

输出样例 1

90

输入样例 2

4 -1 -1 1 0
1 1
-1 1
-1 -1
1 -1

输出样例 2

36.86989764584401285674

说明

两条直线之间的夹角始终在 0 到 90 度之间。下方展示了两个样例的示意图,图中包含初始位置以及具有最大夹角的一种可能最终位置。

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.