← 返回题目列表

Codeforces · 838/E

E. 凸面计数

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

给定一个有 n 个顶点的严格凸多边形。保证没有三点共线。您希望在最多访问每个点一次的多边形顶点上采用最大不相交路径。

更具体地说,您的路径可以表示为某些不同多边形顶点的序列。您的路径是相邻顶点之间按顺序排列的直线段。除了序列中的顶点之外,这些线段不允许彼此接触或相交。

给定多边形,打印最多访问每个点一次的最大长度非相交路径。

输入

输入的第一行将包含一个整数 n (2 ≤ n ≤ 2 500),即点数。

接下来的 n 行将包含两个整数 xi, yi (|xi|, |yi| ≤ 109),表示第 i 个顶点的坐标。

保证这些点按顺时针顺序列出。

输出

打印一个浮点数,表示最多访问顶点一次的最长非相交路径。

如果您的答案的绝对或相对误差最多为 10 - 9,则您的答案将被接受。更具体地说,如果您的答案是 a 而陪审团的答案是 b,则您的答案将被接受,前提是 $${ \frac { | } a - b | } { \operatorname* { m a x } ( 1, b ) } } \leq 1 0 ^ { - 9 }$$。

示例

输入 #1

4
0 0
0 1
1 1
1 0

输出 #1

3.4142135624

注意

一条最佳路径是按顺序访问点 0、1、3、2。