Решение задачи "Хранители" с Codeforces

Без пояснения   Просмотров: 12


Хранители в опасности, и Доктор Манхэттен со своим другом Дэниелом Драйбергом должны срочно их предупредить. Всего в команде хранителей n человек, i-й из которых находится в точке плоскости с координатами (x i, y i).

Как всем известно, доктор Манхэттен вычисляет расстояние между двумя хранителями i и j по формуле |x i - x j| + |y i - y j|. Дэниел, как обычный человек, считает, что расстояние равно .

Сейчас успех операции зависит от того, сколько существует пар (i, j) (1 ≤ i < j ≤ n), таких что расстояние между хранителем i и хранителем j, вычисленное Доктором Манхэттеном, равняется расстоянию между ними, вычисленному Дэниелом. Вычислить эту величину попросили именно вас.

Код

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define mp make_pair
int main ()
{
    map<ll,ll>x1;
    map<ll,ll>y1;
    map<pair<ll,ll>,ll>p1;
    ll n,ans=0;cin>>n;
    while(n--)

    {
        ll x,y;cin>>x>>y;
        ans+=(x1[x]++ + y1[y]++ -p1[mp(x,y)]++);
    }
    cout<<ans;
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться