7911: BZOJ3911：SGU383 Caravans

在这个任务中，你的目标是掠夺商队。 在沙漠中有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佚名上传