codeforces #345 div 2 C. Watchmen (容斥)
题目链接 题意：求曼哈顿距离和平方根距离相等的点的对数？ 思路：化简发现是绝对值乘积等于0，容斥搞搞。
代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年03月07日 星期一 18时43分02秒 4File Name :code/C.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=2E6+7; 34 35struct node 36{ 37 int x,y; 38 39 bool operator < (node b)const 40 { 41 if (x==b.x) return y<b.y; 42 return x<b.x; 43 } 44}p[N]; 45 46 47 48bool cmp( node a,node b) 49{ 50 return a.y<b.y; 51} 52LL cal( LL x) 53{ 54 LL res = x*(x+1)/2; 55 return res; 56} 57int n; 58LL a,b,c; 59LL cnta,cntb,cntc; 60int main() 61{ 62 #ifndef ONLINE_JUDGE 63 freopen("code/in.txt","r",stdin); 64 #endif 65 66 ios::sync_with_stdio(false); 67 cin>>n; 68 for ( int i = 1 ;i <= n ; i++) cin>>p[i].x>>p[i].y; 69 70 sort(p+1,p+n+1); 71 72 a=b=c=0LL; 73 cnta=cntb=cntc=0LL; 74 75 76 for ( int i = 1 ; i <= n-1 ; i++) 77 { 78 if (p[i].x==p[i+1].x) 79 { 80 cnta++; 81 } 82 else 83 { 84 a+=cal(cnta); 85 cnta = 0 ; 86 } 87 } 88 a +=cal(cnta); 89 90 91 for ( int i = 1 ; i <= n-1 ; i++) 92 { 93 if (p[i].x==p[i+1].x&&p[i].y==p[i+1].y) 94 { 95 cntc++; 96 } 97 else 98 { 99 c +=cal(cntc); 100 cntc = 0 ; 101 } 102 } 103 104 c+=cal(cntc); 105 106 107 108 sort(p+1,p+n+1,cmp); 109 for ( int i = 1 ; i <= n-1 ; i ++) 110 { 111 if (p[i].y==p[i+1].y) 112 { 113 cntb++; 114 } 115 else 116 { 117 b +=cal(cntb); 118 cntb = 0 ; 119 } 120 } 121 b +=cal(cntb); 122 123 LL ans=0LL; 124 ans = a+b-c; 125 cout<<ans<<endl; 126 127 #ifndef ONLINE_JUDGE 128 fclose(stdin); 129 #endif 130 return 0; 131}