记录编号	234117	评测结果	AAAAAAAAAA
题目名称	[SPOJ 1960] 矩形	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	2.978 s
提交时间	2016-03-06 21:31:14	内存使用	977.42 MiB

#include<cstdio>
#include<deque>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
using namespace std;
const int SIZEN=250010;
typedef long long LL;
int totx=0,toty=0;
deque<int> posy[SIZEN];
int posx[SIZEN];
int X[SIZEN],Y[SIZEN];
int N;
LL ans=0;
class miku
{
public:
	int x,y;
}P[SIZEN];
int get() {
  int ans=0;
  char tmp=getchar();
  int now=1;
  while((tmp<'0'||tmp>'9')&&tmp!='-') tmp=getchar();
  if(tmp=='-') now=-1,tmp=getchar();
  while(tmp>='0'&&tmp<='9'){
      ans=ans*10+tmp-'0';
      tmp=getchar(); 
  }
  ans*=now;
  return ans;
}
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++) 
	{
		scanf("%d%d",&P[i].x,&P[i].y);
		X[++totx]=P[i].x;
		Y[++toty]=P[i].y;
	}
}
void prepare()
{
	sort(X+1,X+totx+1);
	totx=unique(X+1,X+totx+1)-X-1;
	for(int i=1;i<=N;i++) P[i].x=lower_bound(X+1,X+totx+1,P[i].x)-X;
	sort(Y+1,Y+toty+1);
	toty=unique(Y+1,Y+toty+1)-Y-1;
	for(int i=1;i<=N;i++) P[i].y=lower_bound(Y+1,Y+toty+1,P[i].y)-Y;
}
int best;
deque<int> Q1;//这是要用算法一处理的行
deque<int> Q2;//这是要用算法二处理的行
bool sp[SIZEN]={0};//当前这一行是否处理过
void planA()
{
	bool H[SIZEN];
	for(int i=0;i<Q1.size();i++)
	{
		int x=Q1[i];
		sp[x]=1;
		//cout<<x<<endl;
		for(int j=0;j<posy[x].size();j++) 
		{
			int y=P[posy[x][j]].x;
			H[y]=1;
			//cout<<y<<" ";
		}
		//cout<<endl;
		for(int j=1;j<=toty;j++)
		{
			LL now=0;
			if(sp[j]) continue;
			for(int k=0;k<posy[j].size();k++) 
			{
				int y=P[posy[j][k]].x;
				if(H[y]) now++;
			}
			ans+=now*(now-1);
			//cout<<j<<" "<<now<<endl;
		}
		for(int j=0;j<posy[x].size();j++) 
		{
			int y=P[posy[x][j]].x;
			H[y]=0;
		}
	}
}
miku line[SIZEN*500];
bool cmp(miku a,miku b)
{
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
void planB()
{
	int tot=0;
	for(int k=0;k<Q2.size();k++)
	{
		int x=Q2[k];
		for(int i=0;i<posy[x].size();i++)
		{
			for(int j=i+1;j<posy[x].size();j++)
			{
				int temx=P[posy[x][i]].x,temy=P[posy[x][j]].x;
				line[++tot].x=temx,line[tot].y=temy;
				if(line[tot].x>line[tot].y) swap(line[tot].x,line[tot].y);
			}
		}
	}
	sort(line+1,line+1+tot,cmp);
	//for(int i=1;i<=tot;i++) cout<<line[i].x<<" "<<line[i].y<<endl;
	int i=1,j;
	while(i<tot)
	{
		j=i+1;
		while(j<=tot&&line[i].x==line[j].x&&line[i].y==line[j].y) j++;
		LL now=j-i;
		ans+=now*(now-1);
		i=j;
	}
}
void work()
{
	for(int i=1;i<=N;i++) posy[P[i].y].push_back(i);
	best=sqrt(N+1.0);
	for(int i=1;i<=toty;i++) 
		if(posy[i].size()>best) Q1.push_back(i);
	else Q2.push_back(i);
	//cout<<Q1.size()<<" "<<Q2.size()<<endl;
	planA();
	planB();
	ans/=2;
	printf("%lld",ans);
}
int main()
{
	freopen("RECTANGL.in","r",stdin);
	freopen("RECTANGL.out","w",stdout);
	read();
	prepare();
	//for(int i=1;i<=N;i++) cout<<P[i].x<<" "<<P[i].y<<endl;
	work();
	return 0;
}