题目大意：平面上一堆点，用两条平行于坐标轴的直线将其分为四部分，使得点数最多的一部分最少
第一维枚举，第二维三分，点集用两棵树状数组维护
#include<bits/stdc++.h> #define maxn 100010 using namespace std; inline int read(){ int s=0;char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar()); for(;ch>='0'&&ch<='9';ch=getchar())s=s*10+ch-'0'; return s; } int n; struct node{ int x,y; int cntx,cnty; }s[maxn]; int cmp1(node a,node b){return a.x<b.x;} int cmp2(node a,node b){return a.y<b.y;} int c1[maxn]; int c2[maxn]; void add(int a[],int x,int v){ for(;x<=n;x+=x&-x)a[x]+=v; } int ask(int a[],int x){ int ans=0; for(;x;x-=x&(-x))ans+=a[x]; return ans; } int get(){ int L=1,R=n,mid1,mid2,k1,k2,p1,p2; int sum1=ask(c1,n); int sum2=ask(c2,n); while(R-L>=3){ mid1=(L+L+R)/3,mid2=(L+R+R)/3; p1=ask(c1,mid1);p2=ask(c2,mid1); k1=max(max(p1,sum1-p1),max(p2,sum2-p2)); p1=ask(c1,mid2);p2=ask(c2,mid2); k2=max(max(p1,sum1-p1),max(p2,sum2-p2)); if(k1>k2)L=mid1;else R=mid2; } int ans=(1<<30); for(int i=L;i<=R;++i){ p1=ask(c1,i);p2=ask(c2,i); ans=min(ans,max(max(p1,sum1-p1),max(p2,sum2-p2))); }return ans; } int main(){ freopen("Load_Balancing.in","r",stdin); freopen("Load_Balancing.out","w",stdout); n=read(); for(int i=1;i<=n;++i){ s[i].x=read();s[i].y=read(); } sort(s+1,s+n+1,cmp2); s[1].cnty=1; for(int i=2;i<=n;++i) if(s[i].y==s[i-1].y)s[i].cnty=s[i-1].cnty; else s[i].cnty=s[i-1].cnty+1; sort(s+1,s+n+1,cmp1); s[1].cntx=1; for(int i=2;i<=n;++i) if(s[i].x==s[i-1].x)s[i].cntx=s[i-1].cntx; else s[i].cntx=s[i-1].cntx+1; for(int i=1;i<=n;++i)add(c2,s[i].cnty,1); int L=1,R=s[n].cntx,now=1,ans=(1<<30); for(int i=L;i<=R+1&&now<=n;++i){ while(s[now].cntx<=i&&now<=n)add(c2,s[now].cnty,-1),add(c1,s[now].cnty,1),now++; int k=get(); if(k<ans)ans=k; }printf("%d ",ans); return 0; }