#P15860. [蓝桥杯第二届国际赛] 战线

    ID: 19915 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度提高+/省选− 上传者: 标签>计算几何2018Special Judge凸包蓝桥杯国赛

[蓝桥杯第二届国际赛] 战线

背景

根据蓝桥杯原题样例,应当为“算出最大的危险值”。题面进行了修改。

题目描述

A 国和 B 国正在进行战争,战争极其惨烈,两国都深感资源匮乏,于是两国准备进行和谈。

和谈的一项重要内容就是确定两国的边界。在一个平面上,A 国和 B 国的军事中心分别位于 A=(XA,YA)A=(X_A, Y_A),B=(XB,YB)B=(X_B, Y_B),平面中另有 nn 个标志性建筑,分别位于 (x1,y1),(x2,y2),…,(xn,yn)(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)。

为了方便建设,两国准备选取两个标志性建筑的连线作为边界。但他们都怀疑对手可能背后搞鬼在合约签定后私自开战,显然如果边界上某一点距离两个军事中心的距离差太大,则距离近的那一方可以很快的从军事中心调遣部队进攻该点,而距离远的那一方需要花很多的时间才能增援。所以他们定义一个边界的危险值为:对于这个边界上的任何一个点,该点距离两个军事中心的距离差的最大值(即对于线上的每一个点 XX,∣AX−BX∣|AX-BX| 的最大值)。你作为当时公认的算法界大佬,被要求在很快的速度之内解决这个问题,你需要算出边界最大的危险值。

输入格式

第一行五个整数 n,XA,YA,XB,YBn, X_A, Y_A, X_B, Y_B。

接下来 nn 行,每行两整数,第 ii 行输入 xi,yix_i, y_i。

输出格式

一行一个浮点数,表示最大的危险值,要求误差不超过 10−610^{-6},可以输出多于或少于 66 位小数。

3 -5 0 5 0
2 1
1 0
2 2
7.2111025509

提示

【数据规模和约定】

对于全部数据 2≤n≤1000002 \le n \le 100000,所有坐标绝对值小于等于 10910^9。至少存在两个位置不同的建筑。