记录编号	244007	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO Feb15]负载平衡(白金组)	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	1.637 s
提交时间	2016-03-31 09:58:24	内存使用	4.89 MiB

/*
Writer:ZLX
Date:2016.3.31
Solve:

萌萌哒的题
如果直接暴力枚举a,b,O(n^2)就会超时
我们发现如果如果固定x坐标，y轴上移，则上方的点一定减少
下方的点一定增加，所以题目要求最小值先减小后增大
所以用树状数组维护某个点四个坐标系内的点数
然后枚举一个轴，三分另一个轴即可
时间复杂度O(n*sanfen())
*/
#include <fstream>
#include <algorithm>
#include <map>
#define N 100010
using namespace std;
ifstream cin("Load_Balancing.in");
ofstream cout("Load_Balancing.out");
int INF=(1<<28);
int n,ans=0;
int high[2*N+20]={0},righ[2*N+20]={0};//high(i)表示纵坐标大于i的所有点，righ(i)表示横坐标大于i的所有点(离散化后)
int endpo[N]={0};
class point//点
{
public:
	int x,y;
	void make(int a,int b){x=a;y=b;}
	void print(){cout<<x<<' '<<y<<endl;}
}P[N];
//三种排序
bool com(point a,point b)
{
	if(a.x==b.x)return a.y>b.y;
	return a.x>b.x;
}
bool som(point a,point b)
{
	if(a.y==b.y)return a.x>b.x;
	return a.y>b.y;
}
bool bom(point a,point b)
{
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
//离散化专用
map<int,int> F,G;
int C[N],D[N],E[N];
int m=0,mm=0,O;
void lisanhua()
{
	int i;
	for(i=1;i<=n;i++)C[i]=P[i].y;
	sort(C+1,C+n+1);
	for(i=1;i<n;i++)if(C[i]==C[i+1])C[i]=-1;
	for(i=1;i<=n;i++)if(C[i]!=-1)D[++m]=C[i];
	for(i=1;i<=m;i++)F[D[i]]=i;
	for(i=1;i<=n;i++)P[i].y=2*F[P[i].y]+1;
	
	for(i=1;i<=n;i++)C[i]=P[i].x;
	sort(C+1,C+n+1);
	for(i=1;i<n;i++)if(C[i]==C[i+1])C[i]=-1;
	for(i=1;i<=n;i++)if(C[i]!=-1)E[++mm]=C[i];
	for(i=1;i<=mm;i++)G[E[i]]=i;
	for(i=1;i<=n;i++)P[i].x=2*G[P[i].x]+1;//保证离散化后仍是奇数
	
	O=2*m+10;
}
int Fenwick[2*N+20]={0};//树状数组维护逆序对
void add(int x,int c)
{
	for(int i=x;i>0;i-=(i&(-i)))Fenwick[i]+=c;
}
int sum(int x)
{
	int S=0;
	for(int i=x;i<=O;i+=(i&(-i)))S+=Fenwick[i];
	return S;
}
void read()
{
	int i;
    cin>>n;
	for(i=1;i<=n;i++)cin>>P[i].x>>P[i].y;
	lisanhua();
}
void work()
{
	int i;//树状数组维护二维坐标逆序对从而求出以某个点右边和上边的点
	sort(P+1,P+n+1,com);
	for(i=1;i<=n;i++)add(P[i].y-1,1);
	for(i=1;i<=O;i++)high[i]=sum(i);
	sort(P+1,P+n+1,som);
	for(i=1;i<=O;i++)Fenwick[i]=0;
	
	for(i=1;i<=n;i++)add(P[i].x-1,1);
	for(i=1;i<=O;i++)righ[i]=sum(i);
	for(i=1;i<=O;i++)Fenwick[i]=0;
}
void fuck()
{
	int i,step=0;
	sort(P+1,P+n+1,com);
	for(i=1;i<=n;i++)if(P[i].x!=P[i+1].x)endpo[++step]=i;
	//for(i=1;i<=n;i++)P[i].print();
}
int f(int x,int y)//f(x,y)表示以点x,y生成的坐标系四个象限的点的个数的最大值的最小值
{
	int x1,x2,y1,y2;
	x1=sum(y);//右上角
	x2=high[y]-x1;//上-右上=左上
	y1=righ[x]-x1;//右-右上=右下
	y2=n-x1-x2-y1;//总共减右上右下左上=左下
	return max(max(x1,x2),max(y1,y2));
}
int sanfen(int x,int L,int R)//三分答案
{
	int i;
	double l,r,m1,m2;
	l=(double)L;r=(double)R;
	for(i=0;i<=31;i++)
	{
		m1=l+(r-l)/3;
		m2=r-(r-l)/3;
		if(f(int(x),int(m1*2))<f(int(x),int(m2*2)))r=m2;
		else l=m1;
	}
	return min(f(int(x),int(l*2)),f(int(x),int(r*2)));
}
void buck()
{
	int i,l=1,temp;
	ans=INF;
	for(i=1;i<=n;i++)
	{
		add(P[i].y-1,1);
		if(i==endpo[l])
		{
			l++;
			temp=sanfen(P[i].x-1,-1,O/2);
			ans=min(ans,temp);
		}
	}
	cout<<ans<<endl;
}
int main()
{
	read();
	work();
	fuck();
	buck();
	//不要在意最后的函数名，作者当时调试已经快疯了
	return 0;
}