记录编号 | 234117 | 评测结果 | AAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [SPOJ 1960] 矩形 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | 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; }