fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. typedef pair<int, int> pii;
  6. typedef pair<ll, ll> pll;
  7. typedef vector<int> vi;
  8. typedef vector<ll> vll;
  9. #define pb push_back
  10. #define ff first
  11. #define ss second
  12.  
  13. const int N = 1e5 + 1;
  14. const int b = 320;
  15.  
  16. struct haszownik{
  17.     ll operator()(pii p) const noexcept{
  18.         ll x = p.first, y = p.second;
  19.  
  20.         return (x << 32) | y;
  21.     }
  22. };
  23.  
  24.  
  25. int main(){
  26.     ios_base::sync_with_stdio(0);
  27.     cin.tie(0);
  28.  
  29.     int n;
  30.     cin >> n;
  31.  
  32.     unordered_map<int, unordered_map<int, int>> wiersze;
  33.     unordered_map<int, int> ile;
  34.     unordered_map<pii, ll, haszownik> pary;
  35.     vi ciezkie, lekkie;
  36.     for(int i = 1; i <= n; i++){
  37.         int x, y; cin >> x >> y;
  38.         wiersze[x][y]++;
  39.         ile[x]++;
  40.     }
  41.  
  42.     for(auto& pk : ile){
  43.         if(pk.ss >= b) ciezkie.pb(pk.ff);
  44.         else lekkie.pb(pk.ff);
  45.     }
  46.  
  47.  
  48.     ll wyn = 0;
  49.  
  50.     int m = ciezkie.size();
  51.     for(int i = 0; i < m; i++){
  52.         for(int j = i + 1; j < m; j++){
  53.             int x1 = ciezkie[i], x2 = ciezkie[j];
  54.             if(ile[x1] > ile[x2]) swap(x1, x2);
  55.             ll cnt = 0;
  56.             for(auto& t : wiersze[x1]){
  57.                 int y = t.ff;
  58.                 if(wiersze[x2].find(y) != wiersze[x2].end()) cnt++;
  59.             }
  60.             wyn += (cnt - 1) * cnt / 2;
  61.         }
  62.     }
  63.     int k = lekkie.size();
  64.     for(int i = 0; i < m; i++){
  65.         for(int j = 0; j < k; j++){
  66.             int x1 = lekkie[j], x2 = ciezkie[i];
  67.             ll cnt = 0;
  68.             for(auto& t : wiersze[x1]){
  69.                 int y = t.ff;
  70.                 if(wiersze[x2].find(y) != wiersze[x2].end()) cnt++;
  71.             }
  72.             wyn += (cnt - 1) * cnt / 2;
  73.         }
  74.     }
  75.  
  76.     for(int i = 0; i < k; i++){
  77.         int x = lekkie[i];
  78.         vi elem;
  79.         for(auto& t : wiersze[x]) elem.pb(t.ff);
  80.         int z = elem.size();
  81.         for(int j = 0; j < z; j++){
  82.             for(int l = j + 1; l < z; l++){
  83.                 int y1 = elem[j], y2 = elem[l];
  84.                 if(y1 > y2) swap(y1, y2);
  85.                 wyn += pary[make_pair(y1, y2)];
  86.                 pary[make_pair(y1, y2)]++;
  87.             }
  88.         }
  89.     }
  90.  
  91.  
  92.  
  93.     cout << wyn << "\n";
  94.  
  95.  
  96.  
  97.  
  98.  
  99.     return 0;
  100. }
  101.  
  102.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
7
0 0
0 1
0 4
1 0
1 1
2 0
2 4
stdout 
2
https://ideone.com/53oD4r
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!