You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在红警中，宝石矿是一个很重要的资源，你需要让你的采矿车行驶到宝石矿采集宝石。

红警的地图可以抽象为一个平面直角坐，地图上只有一片宝石矿，区域为一个四条边均与坐标轴平行的矩形，你有 $n$ 个采矿车，分别在 $(x_i,y_i)$ 点，你需要求出所有采矿车中到宝石矿的距离（保留小数点后 $9$ 位），和距离最近的采矿车编号，如果有多个距离宝石矿最近的采矿车，则输出编号最小的采矿车。

采矿车到宝石矿的距离定义为表示采矿车所在的点与表示宝石矿的矩形上所有点（包括四条边上的点和四个顶点）的欧几里得距离的最小值。其中点 $(x_1,y_1)$ 到点 $(x_2,y_2)$ 的欧式几何距离为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ 。

输入格式

第一行包含一个整数 $n$，表示采矿车的个数。

第二行包含四个整数 $X_1, Y_1, X_2, Y_2$ ，$(X_1, Y_1)$ 表示宝石矿左下角的坐标，$(X_2, Y_2)$ 表示宝石矿右上角的坐标。

接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i, y_i$，表示编号为 $i$ 的采矿车的坐标为 $(x_i, y_i)$。保证不会有采矿车在宝石矿的内部或边界上。

输出格式

输出一共两行。

第一行 $n$ 个整数，第 $i$ 个数表示 $i$ 每个采矿车到矿区的最短距离（保留小数点后 $9$ 位）。

第二行一个整数，表示距离最近的采矿车编号。

样例

4
-2 -4 1 -2
9 -7
6 2
-5 10
-9 -7

8.544003745 6.403124237 12.369316877 7.615773106 
2

数据范围

对于 $100\%$ 的数据，保证：$1 \leq n\le 10^5,-100\le X_1,X_2,Y_1,Y_2,x_i,y_i\le 100$，$X_1\le X_2,Y_1\le Y_2$

$\text{A}:$ $X_1=X_2,Y_1=Y_2$

$\text{B}:$ $X_1+1=X_2,Y_1+1=Y_2$