Responsive image

问题 E: 无线网络

问题 E: 无线网络

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 10
[提交][状态][讨论版][命题人:]

题目描述

农夫约翰的农场可以看作一个二维平面。

农场中散布着 nn 头奶牛,每头奶牛的位置坐标已知。

农场中还建有 22 个 wifi 基站,每个基站的位置坐标已知。

这 n+2n+2 个位置坐标两两不同。

第一个基站的有效覆盖范围 r1r1 和第二个基站的有效覆盖范围 r2r2 均可由约翰自由设定。

因为奶牛喜欢保持电子邮件联系,所以约翰希望所有奶牛都能被无线网络覆盖。

如果一头奶牛满足以下两个条件中的至少一个:

  • 它到第一个基站的距离不超过 r1r1
  • 它到第二个基站的距离不超过 r2r2

那么就视为它已被无线网络覆盖。

同时为了降低成本,约翰希望 r12+r22r12+r22 尽可能小。

请你计算 r12+r22r12+r22 的最小可能值。

输入描述

第一行包含 55 个整数 n,x1,y1,x2,y2n,x1,y1,x2,y2,其中 nn 为奶牛数量,(x1,y1)(x1,y1) 为第一个基站的坐标,(x2,y2)(x2,y2) 为第二个基站的坐标。

接下来 nn 行,每行包含两个整数 xi,yixi,yi,表示一头奶牛的位置坐标 (xi,yi)(xi,yi)

输出描述

输出 r12+r22r12+r22 的最小可能值,答案四舍五入到个位。

样例输入

2 -1 0 5 3
0 2
5 2

样例输出

6

提示

所有测试点满足 1≤n≤2000−107≤xi,yi≤107

[提交][状态]
ACM算法攻关部
  • Anything about this OnlineJudge, Please Contact Administrator. Click add QQ

    OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap

    Copyright 2016 ACM算法攻关部
    关于网站改版