计算几何

Title typedef long long LL; typedef vector<int> VI; typedef vector<VI> VVI; const LL INF=0x3f3f3f3f3f3f3f3f; inline LL sqr(LL x){ return x*x; } inline LL dis(const VI &a,const VI &b) { return sqr(a[0]-b[0])+sqr(a[1]-b[1]); } bool cmp(const VI &a, const VI &b) { return a[1]<b[1]; } VVI tmp; LL help(VVI &ps,int l,int r) { int n=r-l+1; if(n<=3) { LL ans=INF; for(int i=l;i<=r;i++) { for(int j=i+1;j<=r;j++) ans=min(ans,dis(ps[i],ps[j])); } sort(ps.begin()+l, ps.begin()+r+1, cmp); return ans; } int m=(l+r)>>1; int mp=ps[m][0]; LL ans=min(help(ps,l,m),help(ps,m+1,r)); int i=l,j=m+1,p=l; while(i<=m || j<=r) { if(i>m || j<=r&&cmp(ps[j],ps[i])) { tmp[p++]=ps[j++]; } else { tmp[p++]=ps[i++]; } } copy(tmp.begin()+l, tmp.begin()+r+1,ps.begin()+l); p=0; for(int i=l;i<=r;i++) { if(sqr(ps[i][0]-mp) …