D. Volatile Kite

Codeforces

IDCF801D

Time2000ms

Memory256MB

Difficulty—

brute forcegeometrygreedy

English · Original

Chinese · Translation

Formal · Original

You are given a convex polygon _P_ with _n_ distinct vertices _p_1, _p_2, ..., _p__n_. Vertex _p__i_ has coordinates (_x__i_, _y__i_) in the 2D plane. These vertices are listed in clockwise order. You can choose a real number _D_ and move each vertex of the polygon a distance of at most _D_ from their original positions. Find the maximum value of _D_ such that no matter how you move the vertices, the polygon does not intersect itself and stays convex. ## Input The first line has one integer _n_ (4 ≤ _n_ ≤ 1 000) — the number of vertices. The next _n_ lines contain the coordinates of the vertices. Line _i_ contains two integers _x__i_ and _y__i_ ( - 109 ≤ _x__i_, _y__i_ ≤ 109) — the coordinates of the _i_\-th vertex. These points are guaranteed to be given in clockwise order, and will form a strictly convex polygon (in particular, no three consecutive points lie on the same straight line). ## Output Print one real number _D_, which is the maximum real number such that no matter how you move the vertices, the polygon stays convex. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6. Namely, let's assume that your answer is _a_ and the answer of the jury is _b_. The checker program will consider your answer correct if . [samples] ## Note Here is a picture of the first sample ![image](https://espresso.codeforces.com/19824412aafab8fcabef388cb9565e54cd80cab6.png) Here is an example of making the polygon non-convex. ![image](https://espresso.codeforces.com/1c6fac549ba45c609730a1c6ac96333bd07c3ff2.png) This is not an optimal solution, since the maximum distance we moved one point is ≈ 0.4242640687, whereas we can make it non-convex by only moving each point a distance of at most ≈ 0.3535533906.

给定一个凸多边形 #cf_span[P]，它有 #cf_span[n] 个互不相同的顶点 #cf_span[p1, p2, ..., pn]。顶点 #cf_span[pi] 在二维平面上的坐标为 #cf_span[(xi, yi)]，这些顶点按顺时针顺序列出。你可以选择一个实数 #cf_span[D]，并将多边形的每个顶点从其原始位置移动最多 #cf_span[D] 的距离。求最大的 #cf_span[D] 值，使得无论你如何移动顶点，多边形都不会自相交且始终保持凸性。第一行包含一个整数 #cf_span[n] (#cf_span[4 ≤ n ≤ 1 000]) —— 顶点的数量。接下来的 #cf_span[n] 行包含各顶点的坐标。第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[ - 109 ≤ xi, yi ≤ 109]) —— 第 #cf_span[i] 个顶点的坐标。这些点保证按顺时针顺序给出，并构成一个严格凸多边形（特别地，任意三个连续点不共线）。输出一个实数 #cf_span[D]，表示最大的实数，使得无论你如何移动顶点，多边形始终保持凸性。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。具体来说，设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，判题程序将认为你的答案正确当且仅当。以下是第一个样例的图示以下是使多边形变为非凸的一个例子。这不是最优解，因为我们移动一个点的最大距离约为 #cf_span[ ≈ 0.4242640687]，而我们只需将每个点移动最多 #cf_span[ ≈ 0.3535533906] 的距离即可使其变为非凸。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[4 ≤ n ≤ 1 000]) —— 顶点的数量。接下来的 #cf_span[n] 行包含各顶点的坐标。第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[ - 109 ≤ xi, yi ≤ 109]) —— 第 #cf_span[i] 个顶点的坐标。这些点保证按顺时针顺序给出，并构成一个严格凸多边形（特别地，任意三个连续点不共线）。 ## Output 输出一个实数 #cf_span[D]，表示最大的实数，使得无论你如何移动顶点，多边形始终保持凸性。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。具体来说，设你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，判题程序将认为你的答案正确当且仅当。 [samples] ## Note 以下是第一个样例的图示。以下是使多边形变为非凸的一个例子。这不是最优解，因为我们移动一个点的最大距离约为 #cf_span[ ≈ 0.4242640687]，而我们只需将每个点移动最多 #cf_span[ ≈ 0.3535533906] 的距离即可使其变为非凸。

**Definitions** Let $ n \in \mathbb{Z} $, $ n \geq 4 $, be the number of vertices. Let $ P = (p_1, p_2, \dots, p_n) $, where $ p_i = (x_i, y_i) \in \mathbb{R}^2 $, be the vertices of a strictly convex polygon given in clockwise order. **Constraints** 1. The polygon $ P $ is strictly convex: for all $ i $, the cross product $ (p_{i+1} - p_i) \times (p_{i+2} - p_{i+1}) < 0 $ (with indices modulo $ n $). 2. No three consecutive points are collinear. 3. Each vertex $ p_i $ may be moved to any point $ p_i' \in \mathbb{R}^2 $ such that $ \|p_i' - p_i\| \leq D $. **Objective** Find the maximum value of $ D \in \mathbb{R}_{\geq 0} $ such that **for all** possible perturbations $ p_i' $ with $ \|p_i' - p_i\| \leq D $, the resulting polygon $ P' = (p_1', \dots, p_n') $ remains strictly convex. This maximum $ D $ equals the minimum over all consecutive triplets of half the distance from the middle vertex to the line through its two neighbors: $$ D = \min_{i=1,\dots,n} \left( \frac{h_i}{2} \right) $$ where $ h_i $ is the perpendicular distance from vertex $ p_i $ to the line through $ p_{i-1} $ and $ p_{i+1} $ (indices modulo $ n $).

Samples

Input #1

Output #1

0.3535533906

Input #2

Output #2

1.0000000000

API Response (JSON)

{
  "problem": {
    "name": "D. Volatile Kite",
    "description": {
      "content": "You are given a convex polygon _P_ with _n_ distinct vertices _p_1, _p_2, ..., _p__n_. Vertex _p__i_ has coordinates (_x__i_, _y__i_) in the 2D plane. These vertices are listed in clockwise order. Yo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF801D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a convex polygon _P_ with _n_ distinct vertices _p_1, _p_2, ..., _p__n_. Vertex _p__i_ has coordinates (_x__i_, _y__i_) in the 2D plane. These vertices are listed in clockwise order.\n\nYo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个凸多边形 #cf_span[P]，它有 #cf_span[n] 个互不相同的顶点 #cf_span[p1, p2, ..., pn]。顶点 #cf_span[pi] 在二维平面上的坐标为 #cf_span[(xi, yi)]，这些顶点按顺时针顺序列出。\n\n你可以选择一个实数 #cf_span[D]，并将多边形的每个顶点从其原始位置移动最多 #cf_span[D] 的距离。\n\n求最大的 #c...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ n \\geq 4 $, be the number of vertices.  \nLet $ P = (p_1, p_2, \\dots, p_n) $, where $ p_i = (x_i, y_i) \\in \\mathbb{R}^2 $, be the vertices of a strictly co...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments