#3911. 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

三角剖分