← 返回题目列表

Codeforces · 1938/I

I. 对称边界

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

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Symmetric Boundary - 原题 PDF 第 1 页
原题PDF第17页
Symmetric Boundary - 原题 PDF 第 2 页
原题PDF第18页
可复制的 PDF 提取文本
Problem I
                 Symmetric Boundary
                     Time limit: 4 seconds


Symmetrical figures are beautiful—and they are the subject of this task. A region in a 2D plane is convex if, for every
pair of points p and q in the region, the segment connecting p and q is entirely included in the region. Also, a region in
a 2D plane is point-symmetric if, when you rotate the region by 180 degrees around a certain point, the rotated region
exactly matches the original region.

You are given a convex polygon in a 2D plane with n vertices, numbered from 1 to n in counterclockwise order.
Vertex i has coordinates (xi, yi). No three vertices are collinear. Determine whether there exists a convex, point-
symmetric region containing all of the n vertices on its boundary.  If one or more such regions exist, compute the
minimum area among all of them.

Input

The first line of input contains one integer n (3 ≤n ≤30). Each of the next n lines contains two integers. The i-th
line contains xi and yi (0 ≤xi, yi ≤1000).

It is guaranteed that the given polygon is convex, its vertices are given in counterclockwise order, and no three of its
vertices are collinear.

Output

If one or more such regions exist, output the minimum area among all of them. The relative error of the output must
be within 10−9.

If such a region does not exist, output -1 instead.


 Sample Input #1                          Sample Output #1
 4                                      90.0
 0 0
 10 0
 8 9
 4 9



 Sample Input #2                          Sample Output #2
 8                                      -1
 8 10
 2 9
 0 8
 0 2
 2 0
 8 0
 10 2
 10 8



ICPC Asia Pacific Championship 2024 Problem I: Symmetric Boundary

Sample Input #3                          Sample Output #3
 6                                      486567.9669655848
 231 77
 359 20
 829 124
 998 461
 941 735
 879 825


Explanation for the sample input/output

Figure I.1 illustrates the vertices in the sample input as black dots. For sample inputs #1 and #3, the shaded regions
represent the regions with the minimum possible area.


    10                                                          10                                                            1000


     8                                                           8                                                             800


     6                                                           6                                                             600


     4                                                           4                                                             400


     2                                                           2                                                             200

     0                                                           0                                                               0
          0       2       4       6       8       10                 0       2       4       6       8       10                 0       200      400      600      800      1000


                         Figure I.1: Illustrations of the sample inputs (from left to right).





ICPC Asia Pacific Championship 2024 Problem I: Symmetric Boundary