[Acwing] 第54场周赛 4429.无线网络

前言

t a g : tag : tag:圆 排序 枚举 传送门 : 题意 : 给定 n n n个那奶牛和两个基站,询问两个基站的 r 1 r1 r1, r 2 r2 r2覆盖半径在覆盖所有奶牛的情况下,他们的 r 1 2 + r 2 2 r_1^2+r_2^2 r12​+r22​最小值是多少

思路 : 显然的,如果我们固定出 r 1 r_1 r1​那么 r 2 r_2 r2​ 也是固定的

同时又因为数据范围 n ≤ 2000 n\le 2000 n≤2000,因此我们考虑枚举 r 1 r_1 r1​,因为 r 1 r_1 r1​可以等于 0 0 0

所以 r 1 ∈ { 0 , D i s i = 1 n ( 奶 牛 , 基 站 1 ) } r1\in\{0,Dis_{i=1}^n(奶牛,基站_1) \} r1∈{0,Disi=1n​(奶牛,基站1​)}

对于我们固定了 r 1 r1 r1,那么范围大于 r 1 r1 r1的奶牛必然需要丢给基站 2 2 2

因此基站 2 2 2的离奶牛的最大半径就是 r 2 r2 r2,因此按此思路模拟即可

优化 :

n l o g n nlogn nlogn的做法是对 r 1 r1 r1的所有距离排序,从大到小枚举

使得每次在 r 1 r1 r1外的点只有一个

code :

pii a[N];
ll cal(pii a,pii b){
	return 1ll*(a.x - b.x)*(a.x - b.x) + 1ll*(a.y - b.y)*(a.y - b.y);
}

void solve(){
	ll n,x1,x2,y1,y2;
	cin>>n>>x1>>y1>>x2>>y2;
	
	for(int i=1;i>a[i].x>>a[i].y;
	
	ll ans = 1e18;
	
	

	for(int i=0;i