【CodeForces - 651C 】Watchmen（map）

Watchmen

直接上中文

Descriptions:

钟表匠们的好基友马医生和蛋蛋现在要执行拯救表匠们的任务。在平面内一共有n个表匠，第i个表匠的位置为(x, y).

他们需要安排一个任务计划，但是确发现了一些问题很难解决。马医生从第i个表匠到第j个表匠所需要的时间为|x - x| + |y - y|。然而蛋蛋所需要的时间为

要想成功完成任务，必须保证两人从第i个表匠出发，同时到达第j个表匠。现在请你计算最多有多少组表匠的位置满足条件

Input

第一行只有一个数n( 1 ≤ n ≤ 200 000) )——代表表匠的数量。

接下来n行，每行两个数x ， y (|x|, |y| ≤ 10).

一些表匠可能位置相同。

Output

输出满足条件的位置的组数。

Examples

Hint

在第一组样例中，马医生从1号走到2号需要的时间为|1 - 7| + |1 - 5| = 10，而蛋蛋需要的时间为

时间不同，然而从1号走到3号，通过同样的方法计算得到马医生和蛋蛋所用的时间相同，均为4；同理从2号到3号也是这样。因此，一共有2组满足题意的位置。

题目链接：
https://vjudge.net/problem/CodeForces-651C

这题有点水吧，用map直接求前一个数有多少的重复的（x），后一个数有几个重复的（y），整体有几个数重复的（z）。让后(x*(x-1）+y*(y-1)+z*(z-1))/2就OK了，是个公式题吧，不明白的小伙伴动手比划比划就知道。

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define mod 1000000007

#define ll long long

#define INF 0x3f3f3f3f

using namespace std;

map<ll,ll> num1;//前一个数x

map<ll,ll> num2;//后一个数y

map<pair<ll,ll>,ll>same;//整体z

map<ll,ll>::iterator it1;

map<pair<ll,ll>,ll>::iterator it2;

ll sum,n,x,y;

int main()

{

    sum=;

    cin>>n;

    for(int i=; i<n; i++)

    {

        cin>>x>>y;

        //查重，看看有多少重复

        num1[x]++;

        num2[y]++;

        same[make_pair(x,y)]++;

    }

    //开始计算

    for(it1=num1.begin();it1!=num1.end();it1++)

    {

        ll t=it1->second;

        sum+=t*(t-)/;

    }

    for(it1=num2.begin();it1!=num2.end();it1++)

    {

        ll t=it1->second;

        sum+=t*(t-)/;

    }

    for(it2=same.begin();it2!=same.end();it2++)

    {

        ll t=it2->second;

        sum-=t*(t-)/;

    }

    cout<<sum<<endl;

}