Description
Watchmen are in a danger and Doctor Manhattan together with his friend Daniel Dreiberg should warn them as soon as possible. There aren.
Sample Input
3 1 1 7 5 1 5
2
6 0 0 0 1 0 2 -1 1 0 1 1 1
11
Hint确实挺好的，明白了题意：求x1=x2||y1=y2的对数，直接循环出错
看博客思路，用结构题分别对x和y排序，算对数，再减x,y都相等时重复的
代码：
#include <cstdio> #include <algorithm> using namespace std; struct Node { int x; int y; }a[200005]; int cmp1(Node a,Node b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int cmp2(Node a,Node b) { if(a.y==b.y) return a.x<b.x; return a.y<b.y; } int main() { int n,i,j; long long ans,cnt,sum; while(~scanf("%d",&n)) { for(i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y); ans=1; cnt=1; sum=0; sort(a,a+n,cmp1);//第一次求对数 for(i=1;i<n;i++) { if(a[i].x==a[i-1].x) { ans++; if(a[i].y==a[i-1].y)//重复的对数 { cnt++; } else { sum-=cnt*(cnt-1)/2; cnt=1; } } else { sum+=ans*(ans-1)/2; sum-=cnt*(cnt-1)/2; cnt=1; ans=1; } } if(ans!=1) sum+=ans*(ans-1)/2; if(cnt!=1) sum-=cnt*(cnt-1)/2; sort(a,a+n,cmp2);//第二次求对数 ans=1; for(i=1;i<n;i++) { if(a[i].y==a[i-1].y) { ans++; } else { sum+=ans*(ans-1)/2; ans=1; } } if(ans!=1) { sum+=ans*(ans-1)/2; } printf("%lld\n",sum); } return 0; }