QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 2048 MB Total points: 100

#10161. Symmetric Boundary

الإحصائيات

对称图形是美丽的,这也是本题的主题。二维平面上的一个区域是凸的,当且仅当对于该区域内的任意两点 $p$ 和 $q$,连接 $p$ 和 $q$ 的线段完全包含在该区域内。此外,二维平面上的一个区域是点对称的,当且仅当将该区域绕某一点旋转 180 度后,旋转后的区域与原区域完全重合。

给定一个二维平面上的凸多边形,其顶点按逆时针顺序编号为 1 到 $n$。顶点 $i$ 的坐标为 $(x_i, y_i)$。任意三点不共线。请判断是否存在一个包含所有 $n$ 个顶点在其边界上的凸点对称区域。如果存在这样的区域,计算所有此类区域中的最小面积。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 30$)。接下来的 $n$ 行,每行包含两个整数。第 $i$ 行包含 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le 1000$)。

保证给定的多边形是凸的,顶点按逆时针顺序给出,且任意三点不共线。

输出格式

如果存在一个或多个这样的区域,输出其中最小的面积。输出的相对误差必须在 $10^{-9}$ 以内。

如果不存在这样的区域,输出 -1。

样例

输入 1

4
0 0
10 0
8 9
4 9

输出 1

90.0

输入 2

8
8 10
2 9
0 8
0 2
2 0
8 0
10 2
10 8

输出 2

-1

输入 3

6
231 77
359 20
829 124
998 461
941 735
879 825

输出 3

486567.9669655848

说明

图 I.1 展示了样例输入中的顶点(黑点)。对于样例 #1 和 #3,阴影区域表示面积最小的区域。

图 I.1:样例输入的示意图(从左到右)。

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.