给定一个有 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。