UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3911. SGU383 Caravans

统计 下载数据

Description

在这个任务中,你的目标是掠夺商队。
在沙漠中有n个绿洲(对于我们而言,它们在平面上的点)。有时商队从一个绿洲到另一个绿洲。为了掠夺它们,你应该预测其路径。但如何做呢?Nomad给出了解决方案。商队的速度是恒定的,他们尽量减少在绿洲外的最长时间。所以,你可以得出结论,即最佳路径是折线。
给定绿洲的坐标和m对商队的线路,出发点为编号为si的绿洲,目的地为编号为ti的绿洲,将最佳路径的最大长度输出。保证所有绿洲位置不同。

Input

第一行一个正整数n为绿洲的数量
接下来n行,每行两个整数x,y表示绿洲在二维平面上的点坐标
接下来一行为一个正整数m为商队数量
接下来m行,每行两个正整数si,ti,为第i个商队的起点和终点

Output

输出m行,每行一个6位小数,为最佳路径上的最大长度

Sample Input

3
0 0
50 10
150 0
3
1 2
1 3
2 3

Sample Output

50.990195
100.498756
100.498756

Hint

n,m<=100000

0<=x,y<100000


三角剖分

Source

By佚名上传