@[Daniel_001](/user/347839) ```priority_queue```是大根堆，你这直接成了找最远的点对了啊
by OldVagrant @ 2022-07-05 16:31:07
应该像dij那样插入其相反数，或者直接重载运算符
by OldVagrant @ 2022-07-05 16:31:37
@[z_z_y](/user/438168) 现在我改过来了，但是不T了，也能过样例，可是全WA……
```cpp
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;
const int maxn = 1e5 + 1;
int ans = 1e18, n, id, cnt = 2, k;//id:当前处理的维度，cnt一共有几维
int lson[maxn], rson[maxn];
priority_queue<int,vector<int>,greater<int> >q;
struct node{
int pos[2], maxx[2], minn[2];
bool operator<(const node&t) const{
return pos[id] < t.pos[id];
}
}a[maxn];
int cheng(int x){return x * x;}
int dis(int x, int y){
return cheng(a[x].pos[1] - a[y].pos[1]) + cheng(a[x].pos[0] - a[y].pos[0]);
}
void push_up(int x, int y){
a[x].minn[0] = min(a[x].minn[0], a[y].minn[0]);
a[x].minn[1] = min(a[x].minn[1], a[y].minn[1]);
a[x].maxx[0] = max(a[x].maxx[0], a[y].maxx[0]);
a[x].maxx[1] = max(a[x].maxx[1], a[y].maxx[1]);
}
int build(int l, int r, int f){
if (l > r) return 0;
if (l == r){
for (int i = 0; i < cnt; i++){
a[l].maxx[i] = a[l].minn[i] = a[l].pos[i];
}
return l;
}
int mid = (l + r) >> 1;
id = f;
nth_element(a + l, a + mid, a + r + 1);
for (int i = 0; i < cnt; i++){
a[mid].maxx[i] = a[mid].minn[i] = a[mid].pos[i];
}
lson[mid] = build(l, mid - 1, !f);
if (lson[mid]) push_up(mid, lson[mid]);
rson[mid] = build(mid + 1, r, !f);
if (rson[mid]) push_up(mid, rson[mid]);
return mid;
}
void add(int x){
if (q.top() > x)return;
q.pop();
q.push(x);
printf("%lld\n", x);
}
int dis1(int x,int y){
int x1 = a[x].minn[0];
int y1 = a[x].minn[1];
int x2 = a[x].maxx[0];
int y2 = a[x].maxx[1];
int x3 = a[y].pos[0];
int y3 = a[y].pos[1];
return max(max(cheng(x1 - x3) + cheng(y1 - y3), cheng(x2 - x3) + cheng(y2 - y3)), max(cheng(x1 - x3) + cheng(y1 - y3), cheng(x2 - x3) + cheng(y2 - y3)));
}
void query(int now,int p){
if(!now) return;
if(now != p) add(dis(now,p));
int be=0;
be=dis1(now,p);
if(be<q.top())return;
if(p<=now)query(rson[now],p),query(lson[now],p);
else query(lson[now],p),query(rson[now],p);
}
signed main(){
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n; i++){
scanf("%lld%lld", &a[i].pos[0], &a[i].pos[1]);
}
int root = build(1, n, 1);
for (int i = 1; i <= 2 * k; i++){
q.push(0);
}
for (int i = 1; i <= n; i++){
query(root, i);
}
printf("%lld\n", q.top());
return 0;
}
```
by Daniel_7216 @ 2022-07-05 16:52:39
艹，忘把调试用的输出删了
by Daniel_7216 @ 2022-07-05 17:05:35