问题描述
为了寻找失去的爱人Cupid，Psyche需要完成Venus的最后一项任务：前往冥界，收集一盒冥界皇后Prosperina的美貌。 冥界有nn个神殿，可以表示为平面上的nn个整点。Psyche想要找到这nn座神殿中，最近的两座神殿之间的距离。传说那就是通往主殿的密码。 但是冥界神秘莫测，在不同的时刻，这nn座神殿中的某一座会消失。 Psyche想要知道，对于nn座神殿中的任意一座消失的情况，最近的两座神殿之间的距离。你只需要输出它们的和。 为避免精度误差，定义两点(x_1, y_1), (x_2, y_2)(x1,y1),(x2,y2)间的距离为d = (x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2d=(x1−x2)2+(y1−y2)2。
输入描述
第一行，一个整数TT (1 \le T \le 5)(1≤T≤5)，代表数据组数。 对于每组数据，第一行，一个整数nn (3 \le n \le 10 ^ 5)(3≤n≤105)，代表神殿个数。 下面nn行，每行两个整数x, yx,y (-10 ^ 5 \le x,y \le 10 ^ 5)(−105≤x,y≤105)，代表神殿的位置在(x, y)(x,y)。 注意可能存在两座神殿坐落在同一位置。
输出描述
输出TT行，对于每组数据，输出nn座神殿中的任意一座消失的情况，最近两座神殿之间的距离的和。
输入样例
1 3 0 0 1 1 2 2
输出样例
12
Hint
神殿(0,0)(0,0)消失时，d = (1-2) ^ 2 + (1 - 2) ^ 2 = 2d=(1−2)2+(1−2)2=2； 神殿(1,1)(1,1)消失时，d = (0-2) ^ 2 + (0 - 2) ^ 2 = 8d=(0−2)2+(0−2)2=8； 神殿(2,2)(2,2)消失时，d = (0-1) ^ 2 + (0-1) ^ 2 = 2d=(0−1)2+(0−1)2=2； 故答案为2 + 8 + 2 = 122+8+2=12。
解题思路：
很裸的平面最近点对的模板题= =题解上的说的也很明确了，只有三种情况
一种情况是删的点不属于最近点对里面的点
剩下两种情况各删的最近点对里面的其中一点
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
const LL inf = 1e18;
struct node{
LL x,y,id;
};
node p[maxn],pp[maxn],tmp[maxn];
LL p1, p2, ans;
LL f(LL x){
return x>=0?x:-x;
}
bool cmp1(node a,node b){
return a.x<b.x;
}
bool cmp2(node a,node b){
return a.y<b.y;
}
LL getDis(node a, node b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
LL Cal_Closest(LL left, LL right, LL step){
LL d=inf;
if(left==right) return d;
if(left+1==right){
LL tmp2 = getDis(p[left],p[right]);
if(step==0){
if(tmp2<ans){
p1 = left;
p2 = right;
ans = tmp2;
}
}
return tmp2;
}
LL mid=(left+right)>>1;
LL d1 = Cal_Closest(left,mid,step);
LL d2 = Cal_Closest(mid+1,right,step);
d = min(d1,d2);
LL k=0;
for(int i=left; i<=right; i++){
if(f(p[mid].x-p[i].x)<=d)
tmp[k++]=p[i];
}
sort(tmp,tmp+k,cmp2);
for(int i=0; i<k; i++){
for(int j=i+1; j<k&&tmp[j].y-tmp[i].y<d; j++){
//d=min(d,getDis(tmp[i],tmp[j]));
if(d>getDis(tmp[i],tmp[j])){
d = getDis(tmp[i],tmp[j]);
if(step==0&&d<ans){
p1=tmp[i].id;
p2=tmp[j].id;
ans=d;
}
}
}
}
return d;
}
int main(){
int t, n;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
memset(p, 0, sizeof(p));
memset(pp, 0, sizeof(pp));
for(int i=0; i<n; i++) scanf("%lld%lld",&p[i].x,&p[i].y);
sort(p,p+n,cmp1);
for(int i=0; i<n; i++) p[i].id=i;
for(int i=0; i<n; i++) pp[i]=p[i];
p1=p2=0;ans=inf;
ans = Cal_Closest(0,n-1,0);
ans=ans*(n-2);
int t=0;
for(int i=0;i<n; i++){
if(pp[i].id==p1) continue;
p[t++]=pp[i];
}
sort(p,p+t,cmp1);
ans += Cal_Closest(0,t-1,1);
t=0;
for(int i=0;i<n; i++){
if(pp[i].id==p2) continue;
p[t++]=pp[i];
}
sort(p,p+t,cmp1);
ans += Cal_Closest(0,t-1,1);
printf("%lld\n", ans);
}
return 0;
}
京公网安备 11010502036488号