abdukodir

Untitled

Mar 7th, 2016
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.68 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <vector>
  5. #include <string>
  6. #include <map>
  7. #include <set>
  8. #include <queue>
  9. #include <stack>
  10. #include <cstring>
  11. #include <algorithm>
  12. #define sc scanf
  13. #define pr printf
  14. #define pb push_back
  15. #define mp std::make_pair
  16. #define fr first
  17. #define se second
  18. #define sqr(i) ((i)*(i))
  19. #define dist(i, j) (sqr(x[i]-x[j]) + sqr(y[i]-y[j]))
  20.  
  21. typedef std::pair<int, int> pii;
  22. typedef std::pair<double, double> pdd;
  23.  
  24. const int MN = 300010;
  25. const int M = 1 << 30;
  26. const long long MAX_LONG = std::numeric_limits<long long>::max();
  27. const int MAX_INT = std::numeric_limits<int>::max();
  28. const int MIN_INT = std::numeric_limits<int>::min();
  29.  
  30. using namespace std;
  31.  
  32. pair<int, int> p[MN];
  33.  
  34. map<int, int>mx;
  35. map<int, int>my;
  36. set<int> sx;
  37. set<int> sy;
  38.  
  39. int main() {
  40. //freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
  41. //freopen("spantree2.in", "r", stdin); freopen("spantree2.out", "w", stdout);
  42. int n;
  43. sc("%d", &n);
  44. for (int i = 0; i < n; i++) {
  45. sc("%d%d", &p[i].fr, &p[i].se);
  46. mx[ p[i].fr ]++;
  47. my[ p[i].se ]++;
  48. sx.insert( p[i].fr );
  49. sy.insert( p[i].se );
  50.  
  51. }
  52.  
  53. sort(p, p + n);
  54.  
  55. long long ans = 0;
  56.  
  57. for(auto a : sx) {
  58. long long cnt = mx[a];
  59. ans += (cnt * (cnt - 1)) / 2;
  60. }
  61.  
  62. for(auto a : sy) {
  63. long long cnt = my[a];
  64. ans += (cnt * (cnt - 1)) / 2;
  65. }
  66.  
  67. for (int i = 0; i < n; ) {
  68. int j = i;
  69. while (j < n && p[i] == p[j]) j++;
  70.  
  71. long long cnt = j - i;
  72.  
  73. ans -= cnt * (cnt - 1) / 2;
  74.  
  75. i = j;
  76. }
  77.  
  78. cout << ans << endl;
  79. return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment