浇花

时间复杂度n^2
按距离其中一个点排序
再找另一个的最大值

n,x1,y1,x2,y2 = map(int, input().split())
flowers = []
for i in range(n):
    x,y = map(int, input().split())
    flowers.append((x,y))
l1,l2 = [], []
l = []
for x,y in flowers:
    distance1 = (x1 - x) ** 2 + (y1 - y) ** 2
    distance2 = (x2 - x) ** 2 + (y2 - y) ** 2
    l.append([distance1, distance2])
l = sorted(l, key=lambda x:x[0])
l.insert(0,[0,0])
l.append([0,0])
res = float("inf")
for i in range(len(l)-1):
    res = min(res, l[i][0] + max(l[i+1:], key=lambda x:x[1])[1])
print(res)

// 抛砖引玉，如果去掉排序，时间复杂度应该是 O(n)
let [num, xa, ya, xb, yb] = readline().split(' ').map(e => e*1), tempX, tempY, dist;
const arrayA=[], arrayB=[];

for(let i=0; i<num; ++i){
    [tempX, tempY] = readline().split(' ').map(e => e*1);
    dist = Math.pow(Math.abs(tempX-xa), 2) + Math.pow(Math.abs(tempY-ya), 2);
    arrayA.push([tempX, tempY, dist]);
}

arrayA.sort((a, b) => a[2] - b[2]);

for(let i=arrayA.length; i>=0; --i){
    if(i === arrayA.length) arrayB[i] = 0;
    else{
        dist = Math.pow(Math.abs(arrayA[i][0]-xb), 2) + Math.pow(Math.abs(arrayA[i][1]-yb), 2);
        arrayB[i] = dist > arrayB[i+1] ? dist : arrayB[i+1];
    }
}

arrayA[-1] = [0, 0, 0];
let min = Number.POSITIVE_INFINITY;

for(let i=-1; i<num; ++i){
    dist = arrayA[i][2] + arrayB[i+1];
    min = min > dist ? dist : min;
}

print(min);

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll Dist(ll x1, ll y1, ll x2, ll y2) {
	return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

struct node{
	ll x, y;
}a[2020];
int mark[2020];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	ll x1, y1, x2, y2;
	ll r1 = 0, r2 = 0;
	ll Min = (ll)1e18 + 10;
	cin >> n >> x1 >> y1 >> x2 >> y2;
	for (int i = 0; i < n; i++) {
		cin >> a[i].x >> a[i].y;
	}
	for (int i = 0; i < n; i++) {
		memset(mark, 0, sizeof(mark));
		r1 = 0;
		r2 = 0;
		r1 = Dist(x1, y1, a[i].x, a[i].y);
		mark[i] = 1;
		for (int j = 0; j < n; j++) {
			if (mark[j]) continue;
			if (Dist(x1, y1, a[j].x, a[j].y) <= r1) {
				mark[j] = 1;
			}
		}
		for (int j = 0; j < n; j++) {
			if (mark[j]) continue;
			r2 = max(r2, Dist(x2, y2, a[j].x, a[j].y));
		}
		Min = min(Min, r1 + r2);
	}
	ll Max = 0;
	for (int i = 0; i < n; i++) {
		Max = max(Max, Dist(x2, y2, a[i].x, a[i].y));
	}
	Min = min(Min, Max);
	Max = 0;
	for (int i = 0; i < n; i++) {
		memset(mark, 0, sizeof(mark));
		r1 = 0;
		r2 = 0;
		r2 = Dist(x2, y2, a[i].x, a[i].y);
		mark[i] = 1;
		for (int j = 0; j < n; j++) {
			if (mark[j]) continue;
			if (Dist(x2, y2, a[j].x, a[j].y) <= r2) {
				mark[j] = 1;
			}
		}
		for (int j = 0; j < n; j++) {
			if (mark[j]) continue;
			r1 = max(r1, Dist(x1, y1, a[j].x, a[j].y));
		}

		Min = min(Min, r1 + r2);
	}
	for (int i = 0; i < n; i++) {
		Max = max(Max, Dist(x1, y1, a[i].x, a[i].y));
	}
	Min = min(Min, Max);
	cout << Min << "\n";
	return 0;
}

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = bf.readLine().split(" ");
        int n = Integer.parseInt(line1[0]);
        int x1 = Integer.parseInt(line1[1]);
        int y1 = Integer.parseInt(line1[2]);
        int x2 = Integer.parseInt(line1[3]);
        int y2 = Integer.parseInt(line1[4]);
        long[][] dis = new long[n][2];
        for (int i = 0; i < n; i++) {
            String[] pos = bf.readLine().split(" ");
            /**
             * 这里不转成 long 类型的话，后面再计算距离时候会出现整数溢出，导致我的通过率一直是20%
             */
            long x = Integer.parseInt(pos[0]);
            long y = Integer.parseInt(pos[1]);
            dis[i][0] = ((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y));
            dis[i][1] = ((x2 - x) * (x2 - x) + (y2 - y) * (y2 - y));
        }
        //根据到喷泉(x1,y1)的距离从大到小进行排序
        Arrays.sort(dis, (a, b) -> b[0] > a[0] ? 1 : -1);
        long ret = Long.MAX_VALUE, d2 = 0;
        /**
         *  当 i = 0,时候,即视为将所有的点归为第一个喷泉，所以 ret = dis[i][0] + 0,每次保存到喷泉2的最大距离，
         *  当 n = i时候，表示前面第 0~i 个点都归为喷泉1，后面i+1~n个点都归为喷泉2，那我们只要记录i+1~n中喷泉2的最大
         *  半径即可，最后需要注意特殊情况，当n个点全部归为喷泉2的情况，即结果要在ret和d2中取最小值
         */
        for (int i = 0; i < n; i++) {
            ret = Math.min(ret, dis[i][0] + d2);
            d2 = Math.max(d2, dis[i][1]);
        }
        System.out.println(Math.min(ret, d2));
    }
}

	//计算每朵花到两个喷泉的距离
	int calDistance(int x, int y, int flow_x, int flow_y) {
		return pow(x - flow_x, 2) + pow(y - flow_y, 2);
	}

	//排序函数，从小到大
	bool static cmp_wf(pair<long, long> pos1, pair<long, long> pos2) {
		if (pos1.first == pos2.first)
		{
			return pos1.second < pos2.second;
		}
		return pos1.first < pos2.first;
	}

	void wateringFlowers() {
		int n, x1, y1, x2, y2;
		//花朵数量，两个喷泉坐标值
		cin >> n >> x1 >> y1 >> x2 >> y2;
		//vector<pair<int, int>> flower(n);
		int flow_x, flow_y;
		long dis1, dis2;
		//每朵花到两个喷泉的距离数组
		vector<pair<long, long>> dis(n);
		//接收花朵坐标值
		for (int i = 0; i < n; i++)
		{
			cin >> flow_x >> flow_y;
			dis1 = calDistance(x1, y1, flow_x, flow_y);
			dis2 = calDistance(x2, y2, flow_x, flow_y);
			dis[i].first = dis1;
			dis[i].second = dis2;
		}
		//考虑喷泉距离为0的情况，为距离数组首添加 (0, 0)
		dis.insert(dis.begin(), make_pair<long, long>(0, 0));
		//排序
		sort(dis.begin(), dis.end(), cmp_wf);
		//尾部插入(0, 0)
		dis.push_back(make_pair<long, long>(0, 0));
		//
		long res = INT_MAX, r1 = 0, r2 = 0;
		for (int i = 0; i < n+1; i++)
		{
			r1 = 0;
			//第1个喷泉到 第[0, i]朵花的最大距离
			for (int j = 0; j <= i; j++)
			{
				r1 = max(r1, dis[j].first);

			}
			r2 = 0;
			//第2个喷泉到 第[i+1, n]朵花的最大距离
			for (int k = i+1; k < n+2; k++)
			{
				r2 = max(r2, dis[k].second);
			}
			//r1 = max(dis[0].first, dis[i].first);
			//r2 = max(dis[i+1].second, dis[n+1].second);
			res = min(res, r1 + r2);
		}
		cout << res << endl;
	}

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x1 = in.nextInt();
        int y1 = in.nextInt();
        int x2 = in.nextInt();
        int y2 = in.nextInt();
        long[][] flowers = new long[n][2];
        for (int i = 0; i < n; i ++) {
            flowers[i][0] = in.nextLong();
            flowers[i][1] = in.nextLong();
        }
        TreeMap<Long, Long> map = new TreeMap<>();
        for (long[] f : flowers) {
            long key = (f[0] - x1) * (f[0] - x1) + (f[1] - y1) * (f[1] - y1);
            long val = (f[0] - x2) * (f[0] - x2) + (f[1] - y2) * (f[1] - y2);
            map.put(key, val);
        }
        long rOne = map.lastKey();
        long rTwo = 0;
        long res = rOne + rTwo;
        while (!map.isEmpty()) {
            rTwo = Math.max(map.pollLastEntry().getValue(), rTwo);
            rOne = map.isEmpty() ? 0 : map.lastKey();
            if (res >= rOne + rTwo) {
                res = rOne + rTwo;
            }
        }
        System.out.println(res);
    }
}

import sys
def dir(a1,b1,a2,b2):
    return (a2-a1)**2+(b2-b1)**2
def ma2(index,lst):
    ma = 0
    for i in range(index+1,len(lst)):
        ma = max(lst[i][1],ma)
    return ma
def ma1(index,lst):
    ma = 0
    for i in range(index+1,len(lst)):
        ma = max(lst[i][0],ma)
    return ma
num,x1,y1,x2,y2 = map(int,input().split())
lst = []
for i in range(num):
    t1,t2 = map(int,input().split())
    lst.append([dir(x1,y1,t1,t2),dir(x2,y2,t1,t2)])
lst.sort(key = lambda x:(x[0]))
res = sys.maxsize
for i in range(len(lst)):
    res = min(lst[i][0]+ma2(i,lst),res)
lst.sort(key = lambda x:(x[1]))
for i in range(len(lst)):
    res = min(lst[i][1]+ma1(i,lst),res)
print(res)