题意与分析 （CodeForces 617C）

题意是这样的：一个花圃中有若干花和两个喷泉，你可以调节水的压力使得两个喷泉各自分别以\(r_1\)和\(r_2\)为最远距离向外喷水。你需要调整\(r_1,r_2\)的值使得所有的花都能被水所灌溉——换句话说，每一朵花要么到第一个喷泉的距离不超过\(r_1\)，要么到第二个喷泉的距离不超过\(r_2\)。当然如果两个条件都满足也是可以的。你需要用尽可能少的水来实现以上要求，也就是说使得\(r_1^2+r_2^2\)尽可能的小。找出这个最小值。

那么问题来了，这里可能会有人YY出一个比较美好的\(O(n)\)的算法：既然每个人都是不是取1就是取2，那么我们遍历一遍，每次遍历选择那个令半径变大尽可能小的，那就完事了。但是并不可以，这样会受到顺序的制约，就是说不同顺序的答案是不一样的，不是正确的贪心。

那么我们只能退而求其次：枚举每个点，硬点它的大小为第一个半径，然后再枚举这\(n\)个点，比它大的就归第二个半径，然后这样一个\(n^2\)的算法就能够得到结果。

更好的是一个\(O(n\log n)\)的算法。先排序（pair），然后维护一个倒序的与第二个喷泉的最大值。这样，当我们循环到第\(i\)个的时候，如果采用第\(i\)个半径，前\(i\)个一定能被覆盖，只要保证剩下的被覆盖就可以了——也就是取我们维护的那个最大值。这其实是上面那个美好的YY的变种。这里就不赘述了。

代码

/*

 * Filename: cfr340d2c.cpp

 * Date: 2018-11-09

 */

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define PB emplace_back

#define MP make_pair

#define fi first

#define se second

#define rep(i,a,b) for(repType i=(a); i<=(b); ++i)

#define per(i,a,b) for(repType i=(a); i>=(b); --i)

#define ZERO(x) memset(x, 0, sizeof(x))

#define MS(x,y) memset(x, y, sizeof(x))

#define ALL(x) (x).begin(), (x).end()

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

using pi=pair<int,int>;

using repType=int;

using ll=long long;

using ld=long double;

using ull=unsigned long long;

int

main()

{

QUICKIO

    ll n,x1,y1,x2,y2; cin>>n>>x1>>y1>>x2>>y2;

    vector<pi> vec;

    rep(i,1,n)

    {

        ll x,y; cin>>x>>y;

        vec.PB(x,y);

    }

    ll minans=9e17;

    rep(i,0,n)

    {

        ll r12,r22=0;

        if(i==n)

            r12=0;

        else r12=(vec[i].fi-x1)*(vec[i].fi-x1)+(vec[i].se-y1)*(vec[i].se-y1);

        rep(j,0,n-1)

        {

            ll tmp1=(vec[j].fi-x1)*(vec[j].fi-x1)+(vec[j].se-y1)*(vec[j].se-y1);

            ll tmp2=(vec[j].fi-x2)*(vec[j].fi-x2)+(vec[j].se-y2)*(vec[j].se-y2);

            if(tmp1<=r12) continue;

            else

            {

                r22=max(tmp2, r22);

            }

        }

        //cout<<r12<<" "<<r22<<endl;

        minans=min(minans, r22+r12);

    }

    cout<<minans<<endl;

    return 0;

}