【原题】

Description

给N个点，问存在多少个两边与坐标轴平行的正方形，四个顶点属于这N个点中的4个。

Input

第一行一个整数N。
接下来N行每行两个数x_i，y_i表示坐标。

Output

一行一个整数表示答案。

Sample Input

Sample Output

HINT

【数据范围】

N<=10^5，|x_i|,|y_i|<=10^6

Source

By Sbullet

【分析】开始感觉用的是类似“边表”的方法（这个比喻不是很恰当啊）。比如对于同一个X，我想边表一样把所有Y都连在一起进行操作。但是后来想：不是还要把Y坐标排序吗？于是就想到了SET。

初始想法：枚举每一个点作为左上角的点，然后枚举X坐标上向右的Y点（作为正方形右上角的点），再枚举Y坐标上向下的X点（作为正方形左下角的点）。最后判断一下右下角的点是否在set中。

还有，直接开2个2*10^6的set会爆内存（把负数变正数），因此我先离散了一下，开了2个10^5的set。

【初始代码】

#include
  
   
#include
   
     #include
    
      #include
     
       #define A 1000000 #define N 100005 using namespace std; typedef set
      
       ::iterator It;It it,r,ok1,ok2; long long ans; set
       
        P[N],Q[N]; int n,x,y1,y2,x1,x2,aa,i,m,rex[A*2+1],rey[A*2+1],point; inline int Read() { int x=0;char ch=getchar();bool positive=1; for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') positive=0; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return positive?x:-x; } struct arr{int x,y;}a[N+1]; bool cmp1(arr a,arr b){return a.x
         
         
 
         
【可惜】超时了。咨询了阳神，想法大致是对的，但很多时间耗费在枚举右上角的点和左下角的点了。可以开一个L和D指针，分别指向右边和下面。设X的set里面向左的Y有P个，Y的set里面向下的X有Q个，原来的效率是P*Q，现在均摊效率就是P+Q。太神了。据杜教说，效率均摊是N^1.5。GL。。。
 
         
【附：造数据程序】
 
         
 
         
#include
          
           
#include
           
             #include
            
              using namespace std; struct arr{int x,y;}a[5000005]; int n,x,y,len,temp,j,i,cnt; int main() { freopen("p.in","w",stdout); srand((int)time(0)); n=25000;int m=500,k=1000; printf("%d\n",n*4); for (i=1;i<=n;i++) { temp=rand()%10; if (!temp) { x=rand()%k-m;y=rand()%k-m;len=rand()%k+1; a[++cnt]=(arr){x,y}; a[++cnt]=(arr){x+len,y+len}; a[++cnt]=(arr){x,y+len}; a[++cnt]=(arr){x+len,y}; } else for (j=1;j<=4;j++) a[++cnt]=(arr){rand()%k-m,rand()%k-m}; } for (i=1;i<=cnt;i++) printf("%d %d\n",a[i].x,a[i].y); return 0; }
            
           
          
 
         
 
         
【AC代码】
 
         
 
         
#include
          
           
#include
           
             #include
            
              #include
             
               #define A 1000000 #define N 100005 using namespace std; typedef set
              
               ::iterator It;It it,r,d,ok1,ok2; long long ans; set
               
                P[N],Q[N]; int n,x,y1,y2,x1,x2,aa,i,m,rex[A*2+1],rey[A*2+1],px,py,cnt,cntt; inline int Read() { int x=0;char ch=getchar();bool positive=1; for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') positive=0; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return positive?x:-x; } struct arr{int x,y;}a[N+1]; bool cmp1(arr a,arr b){return a.x