Codeforces651C Watchmen

题目链接

题意：坐标系中给出 n 个点，有两种计算距离的方法，一种是传统的两点间距离，另一种是横坐标差的绝对值加纵坐标差的绝对值。问 n 个点中这两种算法得到的答案一样的点对有多少个。（不算同一个点）

算出横坐标相等的点的个数存到 vector 里，再存纵坐标，然后遍历 vector 计算 Cn2。最后减去所有重复点的 Cn2。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

vector<int> num;

struct Point{
    int x, y;
}P[200005];

long long cal(int x){
    return (long long)x*(x-1)/2;
}
bool cmp1(Point a, Point b){
    if(a.x != b.x) return a.x<b.x;
    return a.y<b.y;
}
bool cmp2(Point a, Point b){
    if(a.y != b.y) return a.y<b.y;
    return a.x<b.x;
}
int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    P[0].x = 1e9+1;
    P[0].y = 1e9+1;
    while(~scanf("%d", &n)){
        num.clear();
        for(int i = 1; i <= n; i++){
            scanf("%d %d", &P[i].x, &P[i].y);
        }
        sort(P+1, P+n+1, cmp1);
        long long cnt = 1, ans = 0, flag = 1;
        for(int i = 1; i <= n; i++){
            if(P[i].x == P[i-1].x && P[i].y == P[i-1].y){
                cnt++;
                if(i == n){
                    ans += (long long)cnt*(cnt-1)/2;
                    cnt = 1;
                }
            }else if(cnt != 1){
                ans += (long long)cnt*(cnt-1)/2;
                cnt = 1;
            }

            if(P[i].x == P[i-1].x){
                flag++;
                if(i == n){
                    num.push_back(flag);
                    flag = 1;
                }
            }else if(flag != 1){
                //cout << "test" << endl;
                num.push_back(flag);
                flag = 1;
            }
        }
        sort(P+1, P+n+1, cmp2);
        for(int i = 1; i <= n; i++){
            if(P[i].y == P[i-1].y){
                flag++;
                if(i == n){
                    num.push_back(flag);
                    flag = 1;
                }
            }else if(flag != 1){
                num.push_back(flag);
                flag = 1;
            }
        }
        long long ans1 = 0;
        for(int i = 0; i < num.size(); i++){
            //cout << num[i] <<endl;
            ans1 += cal(num[i]);
        }
        ans1 -= ans;

        //break;
        //cout << ans << endl;
        cout << ans1 << endl;
    }
    return 0;
}