QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 512 MB Total points: 100 Hackable ✓
[0]

# 784. 旋转卡壳

Statistics

题目描述

以逆时针顺序给定一个 n 个点的凸多边形(可能存在三点共线),求它的直径。

输入格式

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

接下来 n 行,每行包含两个整数 xi,yi,描述一个点的坐标。

输出格式

输出一行一个实数,表示答案。当你与标准答案的相对误差不超过 106 时将被视为正确。

样例数据

样例 1 输入

3
0 0
4 0
2 2

样例 1 输出

4

样例 2 输入

4
0 0
1 0
1 1
0 1

样例 2 输出

1.414213562373

样例 3 输入

10
0 0
461074 -72768411
3213786 -131277098
9156758 -204048615
50058801 -267750564
98614697 -289078664
138651620 -243972492
191427505 -152569765
131060323 -88251044
85141546 -55035262

样例 3 输出

305436298.50498565947291157209925

子任务

对于所有数据,3n5×105

  • Subtask 1(10 pts): n103
  • Subtask 2(30 pts): n3×104
  • Subtask 3(60 pts): No additional constraints.