#O1060. 凸包周长

凸包周长

题目描述

给定平面上 nn 个互不相同的点,求这些点构成的凸包(最外层凸多边形)的周长,结果保留两位小数。若所有点共线,则周长为两端点之间的线段长度的两倍。

题目类型

计算几何、凸包(Andrew 单调链)

输入格式

第一行一个整数 nn。

接下来 nn 行,每行两个整数 xi,yix_i, y_i。

输出格式

一行一个实数,表示凸包周长,保留两位小数。

样例 #1

样例输入 #1

4
0 0
0 1
1 0
1 1

样例输出 #1

4.00

数据规模与约定

数据范围 说明
1≤n≤1051 \le n \le 10^5 点数
0≤xi,yi≤1090 \le x_i, y_i \le 10^9 坐标
  • 用叉积判断拐向,排序后求上凸壳与下凸壳,答案用 double。