Codeforces 651C Watchmen[시뮬레이션]

제목:

유클리드 거리와 맨해튼 거리가 같은 조수를 구하다.

분석:

간소화 후 xi=xj||yi=yj를 얻으면 x상등+y상등-x와 y가 모두 상등함을 구한다.

코드:

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1000000 + 5;
typedef pair<long long , long long>pii;
pii p[maxn];
bool cmp(pii a, pii b)
{
    return a.first < b.first||(a.first == b.first && a.second < b.second);
}
bool cmp1(pii a, pii b)
{
    return a.second < b.second||(a.second == b.second &&a.first < b.first);
}
int main (void)
{
    int n;cin>>n;
    for(int i = 0; i < n; i++){
       cin>>p[i].first>>p[i].second;
    }
    long long resx = 0, resy = 0;
    long long cnt = 0;
    sort(p, p + n, cmp);
    for(int i = 1; i < n; i++){
       if(p[i].first == p[i - 1].first)
            cnt++;
        if(i == n-1||p[i].first != p[i - 1].first){
           resx += cnt * (cnt + 1)/2;
            cnt = 0;
        }
    }
    sort(p, p + n, cmp1);
    cnt = 0;
    long long  aa = 0, both = 0;
    for(int i = 1; i < n; i++){
        if(p[i].second == p[i - 1].second){
            cnt++;
            if(p[i].first == p[i-1].first)
                aa++;
            if(p[i].first != p[i-1].first){
                both += aa * (aa + 1)/2;
                aa = 0;
            }
        }
        if(i == n-1||p[i].second != p[i - 1].second){
            resy += cnt * (cnt + 1)/2;
            cnt = 0;
            both += aa * (aa + 1)/2;
            aa = 0;
        }
    }
    cout<<resx + resy - both<<endl;
}

맵으로 할 수도 있습니다. 이렇게 하면 x와 y가 똑같은 개수를 직접 기록할 수 있습니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 200005;
typedef pair<int, int> p;
typedef long long ll;
map<int, int>ma, mb;
map<p, int> mp;
int main (void)
{
    int n;cin>>n;
    int x, y;
    for(int i = 0; i < n; i++){
        cin>>x>>y;
        ma[x] ++;
        mb[y]++;
        mp[p(x, y)]++;
    }
    long long resx = 0, resy = 0, both = 0;
    map<int, int>::iterator i;
    map<p, int>::iterator j;
    for(i = ma.begin(); i != ma.end(); i++){
        resx +=(ll) i->second * ( i->second- 1)/2;
    }
    for(i = mb.begin(); i!=mb.end();i++){
        resy += (ll)i->second * ( i->second- 1)/2;
    }
    for(j = mp.begin(); j != mp.end(); j++){
        both += (ll) j->second * ( j->second- 1)/2;
    }
    cout<<resx + resy - both<<endl;
    return 0;
}

C++11의 경우 4for(i = ma.begin(); i != ma.end(); i++)그냥 쓰셔도 돼요.

for(auto x: ma) 

첫 번째 방법인resx,resy,both를 각각 저장하지 않고res에 대해 끊임없이 가감하면 마지막으로runtime error......