QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Hackable ✓

# 218. 二维凸包

Statistics

题目描述

给定二维平面中的 $n$ 个点 $P_i(x_i, y_i)$,求他们组成的凸包的周长。

输入格式

输入的第一行包含一个整数 $n$。

接下来 $n$ 行,每行两个整数 $x_i, y_i$。

输出格式

输出一行一个实数表示答案。要求相对误差或绝对误差不超过 $10^{-6}$。

样例数据

样例 1 输入

5
1 2
1 4
2 3
3 5
4 2

样例 1 输出

10.3983456376681690

样例 2 输入

9
1 3
1 7
2 2
2 5
2 9
3 4
3 6
4 1
5 5

样例 2 输出

19.0094551429903350

子任务

对于 $100\%$ 的数据,$3 \leq n \leq 2 \times 10^5$,$-10^9 \leq x_i, y_i \leq 10^9$。