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佚名上传