SGU383 Caravans
时间限制：30s 空间限制：256MB
题目描述
在这个任务中，你的目标是掠夺商队。
在沙漠中有n个绿洲（对于我们而言，它们在平面上的点）。有时商队从一个绿洲到另一个绿洲。为了掠夺它们，你应该预测其路径。但如何做呢？Nomad给出了解决方案。商队的速度是恒定的，他们尽量减少在绿洲外的最长时间。所以，你可以得出结论，即最佳路径是折线。
给定绿洲的坐标和m对商队的线路，出发点为编号为si的绿洲，目的地为编号为ti的绿洲，将最佳路径的最大长度输出。保证所有绿洲位置不同。
输入格式
第一行一个正整数n为绿洲的数量
接下来n行，每行两个整数x,y表示绿洲在二维平面上的点坐标
接下来一行为一个正整数m为商队数量
接下来m行，每行两个正整数si,ti，为第i个商队的起点和终点
输出格式
输出m行，每行一个6位小数，为最佳路径上的最大长度
样例输入
3 0 0 50 10 150 0 3 1 2 1 3 2 3
样例输出
50.990195 100.498756 100.498756
提示
n,m<=100000
0<=x,y<100000
三角剖分
题目来源
By佚名上传