【Luogu】P4357K远点对（寄蒜几盒）

　　题目链接

　　考虑旋转卡壳求出一个最远点对之后删掉其中一个点，把该点到其余所有点的距离存进堆里……

　　最后堆输出答案。

　　我的代码只有在开O2的情况下才不会re。为啥？？？？

　　

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cctype>
#define maxn 300020
using namespace std;
inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

struct Point{
    long long x,y;
    bool operator ==(const Point a){
        return x==a.x&&y==a.y;
    }
}q[maxn],stack[maxn],d[maxn],sta;
int top,cnt;



inline long long multi(Point a,Point b,Point c){    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);    }
inline long long caldis(Point a,Point b){    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);    }
inline int calcnxt(int a,int n){    int b=a+1;    if(b>n)    b=1;    return b;    }
inline bool cmp(Point a,Point b){    return multi(sta,a,b)!=0?multi(sta,a,b)>0:a.x<b.x;    }

long long heap[maxn*100],size;
inline void push(long long x){
    heap[++size]=x;
    int i=size,k;
    while(i>1){
        k=i>>1;
        if(heap[k]<=heap[i])    return;
        swap(heap[k],heap[i]);
        i=k;
    }
    return;
}
inline long long pop(){
    long long ans=heap[1];    heap[1]=heap[size--];
    int i=1,k;
    while(i*2<=size){
        k=i<<1;
        if(k<size&&heap[k]>heap[k|1])    k|=1;
        if(heap[i]<=heap[k])    return ans;
        swap(heap[i],heap[k]);
        i=k;
    }
    return ans;
}

void prepare(int from,int to,int deep){
    if(deep==0)    return;
    if(to-from<=2){
        for(int i=from;i<=to;++i)    d[++cnt]=q[i];
        return;
    }
    int now=from;
    for(int i=from;i<=to;++i)
        if(q[i].y<q[now].y||(q[i].y==q[now].y&&q[i].x<q[now].x))    now=i;
    sta=q[now];
    swap(q[now],q[from]);
    sort(q+from+1,q+to+1,cmp);
    top=2;
    stack[1]=q[from];    stack[2]=q[from+1];
    for(int i=from+2;i<=to;++i){
        while(top>1&&multi(stack[top-1],stack[top],q[i])<=0)    top--;
        stack[++top]=q[i];
    }
    stack[++top]=stack[1];
    now=1;
    int ansa=from,ansb=from;
    for(int i=1;i<top;++i){
        int nxt=calcnxt(now,top);
        
        while(multi(stack[i],stack[i+1],stack[now])<=multi(stack[i],stack[i+1],stack[nxt])){
            now=nxt;
            nxt=calcnxt(now,top);
        }
        if(caldis(stack[i],stack[now])>caldis(stack[ansa],stack[ansb])){
            ansa=i;    ansb=now;
        }
        if(caldis(stack[i+1],stack[now])>caldis(stack[ansa],stack[ansb])){
            ansa=i+1;    ansb=now;
        }
    }
    d[++cnt]=stack[ansa];    d[++cnt]=stack[ansb];
    for(int i=from;i<=to;++i)
        if(q[i]==stack[ansa]){
            swap(q[i],q[from]);
            break;
        }
    for(int i=from+1;i<=to;++i){
        push(caldis(q[from],q[i]));
        while(size>deep)    pop();
    }
}

int main(){
    int n=read(),m=read();
    for(int i=1;i<=n;++i)    q[i]=(Point){read(),read()};
    for(int i=1;i<=m;++i)    prepare(i,n,m);
    printf("%lld
",pop());
    return 0;
}