English · Original
Chinese · Translation
Formal · Original
You are given an strictly convex polygon with _n_ vertices. It is guaranteed that no three points are collinear. You would like to take a maximum non intersecting path on the polygon vertices that visits each point at most once.
More specifically your path can be represented as some sequence of distinct polygon vertices. Your path is the straight line segments between adjacent vertices in order. These segments are not allowed to touch or intersect each other except at the vertices in your sequence.
Given the polygon, print the maximum length non-intersecting path that visits each point at most once.
## Input
The first line of input will contain a single integer _n_ (2 ≤ _n_ ≤ 2 500), the number of points.
The next _n_ lines will contain two integers _x__i_, _y__i_ (|_x__i_|, |_y__i_| ≤ 109), denoting the coordinates of the _i_\-th vertex.
It is guaranteed that these points are listed in clockwise order.
## Output
Print a single floating point number, representing the longest non-intersecting path that visits the vertices at most once.
Your answer will be accepted if it has absolute or relative error at most 10 - 9. More specifically, if your answer is _a_ and the jury answer is _b_, your answer will be accepted if .
[samples]
## Note
One optimal path is to visit points 0,1,3,2 in order.
给定一个具有 #cf_span[n] 个顶点的严格凸多边形。保证任意三点不共线。你希望在多边形的顶点上找到一条最长的不相交路径，每个点至多访问一次。
更具体地，你的路径可以表示为一个互不相同的多边形顶点序列。你的路径由按顺序连接相邻顶点的直线段组成。这些线段不允许在除序列中顶点以外的任何地方相交或接触。
给定该多边形，请输出访问每个顶点至多一次的最长不相交路径的长度。
输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2 500])，表示点的数量。
接下来的 #cf_span[n] 行每行包含两个整数 #cf_span[xi, yi] (#cf_span[|xi|, |yi| ≤ 109])，表示第 #cf_span[i] 个顶点的坐标。
保证这些点按顺时针顺序给出。
输出一个浮点数，表示访问顶点至多一次的最长不相交路径的长度。
你的答案若绝对误差或相对误差不超过 #cf_span[10 - 9]，则会被接受。更具体地，若你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，则当 时你的答案会被接受。
一种最优路径是按顺序访问点 0,1,3,2。
## Input
输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2 500])，表示点的数量。接下来的 #cf_span[n] 行每行包含两个整数 #cf_span[xi, yi] (#cf_span[|xi|, |yi| ≤ 109])，表示第 #cf_span[i] 个顶点的坐标。保证这些点按顺时针顺序给出。
## Output
输出一个浮点数，表示访问顶点至多一次的最长不相交路径的长度。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 9]，则会被接受。更具体地，若你的答案为 #cf_span[a]，标准答案为 #cf_span[b]，则当 时你的答案会被接受。
[samples]
## Note
一种最优路径是按顺序访问点 0,1,3,2。
**Definitions**
Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 2500 $ be the number of vertices of a strictly convex polygon.
Let $ P = (p_0, p_1, \dots, p_{n-1}) $ be the sequence of vertices in clockwise order, where $ p_i = (x_i, y_i) \in \mathbb{R}^2 $ and $ |x_i|, |y_i| \leq 10^9 $.
A *non-intersecting path* is a sequence $ \pi = (p_{i_0}, p_{i_1}, \dots, p_{i_k}) $ of distinct vertices such that:
- The straight-line segments $ \overline{p_{i_j}p_{i_{j+1}}} $ for $ j = 0, \dots, k-1 $ do not intersect except possibly at shared endpoints.
- The path is simple (no self-intersections).
The *length* of path $ \pi $ is $ \sum_{j=0}^{k-1} \|p_{i_j} - p_{i_{j+1}}\|_2 $.
**Constraints**
1. The polygon is strictly convex.
2. No three vertices are collinear.
3. Vertices are given in clockwise order.
**Objective**
Find the maximum-length non-intersecting path that visits each vertex at most once. That is, compute:
$$
\max_{\pi \in \mathcal{P}} \sum_{j=0}^{|\pi|-2} \|p_{\pi_j} - p_{\pi_{j+1}}\|_2
$$
where $ \mathcal{P} $ is the set of all simple non-intersecting paths over the vertex set $ \{p_0, \dots, p_{n-1}\} $.
API Response (JSON)
{
"problem": {
"name": "E. Convex Countour",
"description": {
"content": "You are given an strictly convex polygon with _n_ vertices. It is guaranteed that no three points are collinear. You would like to take a maximum non intersecting path on the polygon vertices that vis",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF838E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given an strictly convex polygon with _n_ vertices. It is guaranteed that no three points are collinear. You would like to take a maximum non intersecting path on the polygon vertices that vis...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "给定一个具有 #cf_span[n] 个顶点的严格凸多边形。保证任意三点不共线。你希望在多边形的顶点上找到一条最长的不相交路径，每个点至多访问一次。\n\n更具体地，你的路径可以表示为一个互不相同的多边形顶点序列。你的路径由按顺序连接相邻顶点的直线段组成。这些线段不允许在除序列中顶点以外的任何地方相交或接触。\n\n给定该多边形，请输出访问每个顶点至多一次的最长不相交路径的长度。\n\n输入的第一行包含一个整...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 2500 $ be the number of vertices of a strictly convex polygon. \nLet $ P = (p_0, p_1, \\dots, p_{n-1}) $ be the sequence of vertices in c...",
"is_translate": false,
"language": "Formal"
}
]
}