CodeForces 651 C Watchmen

C. Watchmen

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Watchmen are in a danger and Doctor Manhattan together with his friend Daniel Dreiberg should warn them as soon as possible. There are n watchmen on a plane, the i-th watchman is located at point (xi, yi).

They need to arrange a plan, but there are some difficulties on their way. As you know, Doctor Manhattan considers the distance between watchmen i and j to be |xi - xj| + |yi - yj|. Daniel, as an ordinary person, calculates the distance using the formula 

.

The success of the operation relies on the number of pairs (i, j) (1 ≤ i < j ≤ n), such that the distance between watchman i and watchmen j calculated by Doctor Manhattan is equal to the distance between them calculated by Daniel. You were asked to compute the number of such pairs.

Input

The first line of the input contains the single integer n (1 ≤ n ≤ 200 000) — the number of watchmen.

Each of the following n lines contains two integers xi and yi (|xi|, |yi| ≤ 109).

Some positions may coincide.

Output

Print the number of pairs of watchmen such that the distance between them calculated by Doctor Manhattan is equal to the distance calculated by Daniel.

Examples

input

3
1 1
7 5
1 5

output

2

input

6
0 0
0 1
0 2
-1 1
0 1
1 1

output

11

两种距离相等的情况就是两个点的横坐标相等或者纵坐标相等。这里分别排序一下,然后注意要减去两个点相同的情况

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
#define MAX 200000
struct Node
{
    long long int x;long long int y;

}a[MAX+5];
long long int ans[MAX+5];
int cmp(Node a,Node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
int cmp2(Node a,Node b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}
int n;
long long int ans2[MAX+5];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);
    memset(ans,0,sizeof(ans));
    int cnt=0;
    int cot=0;
    ans[0]=1;
    ans2[0]=1;
    long long int num=1;
    for(int i=2;i<=n;i++)
    {
        //cout<<a[i].x<<" "<<a[i-1].x<<endl;
        if(a[i].x==a[i-1].x)
        {
            if(a[i].y==a[i-1].y)
                ans2[cot]++;
            else
            {
                cot++;
                ans2[cot]=1;
            }
            ans[cnt]++;
        }
        else
        {
            cot++;
            ans2[cot]=1;
            cnt++;
            ans[cnt]=1;
        }
    }
    long long int res=0;
    long long int res2=0;
    for(int i=0;i<=cnt;i++)
    {
        res+=(ans[i]*(ans[i]-1))/2;

    }
    for(int i=0;i<=cot;i++)
    {
        res2+=(ans2[i]*(ans2[i]-1))/2;

    }

    sort(a+1,a+n+1,cmp2);
    memset(ans,0,sizeof(ans));
    cnt=0;
    ans[0]=1;
    for(int i=2;i<=n;i++)
    {
        if(a[i].y==a[i-1].y)
        {
            ans[cnt]++;
        }
        else
        {
            cnt++;
            ans[cnt]=1;
        }
    }
    for(int i=0;i<=cnt;i++)
       res+=(ans[i]*(ans[i]-1))/2;
    printf("%lld\n",res-res2);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MixLab科技+设计实验室

从低保真原型中生成前端代码

今天聊下《 技术 Mix 设计 》的话题。技术与设计两者的边界,越来越模糊,从用机器视觉判断平面设计作品的视觉焦点,到用深度学习指导用户体验设计,还有用深度学习...

36460
来自专栏calmound

Hand in Hand(并查集)

题意:判断两个图形是否相似,根据题意可以知道图形的分量,不是环就是链,所以我们只要依次两个图形是否一样就可以了 分析:若两个图形完全一样的话,那么它们成环和成链...

35170
来自专栏计算机视觉战队

2017年深度学习优化算法最新综述

梯度下降算法是机器学习中使用非常广泛的优化算法,也是众多机器学习算法中最常用的优化方法。几乎当前每一个先进的(state-of-the-art)机器学习库或者深...

33990
来自专栏Python爬虫与算法进阶

来codewars与我一起玩耍吧

先看一道题目 如何使用代码表示“石头、剪刀、布”之间的关系。 即:石头 > 剪刀,剪刀 > 布, 剪刀 > 布 当时我想了很多,构造一个字典,和数字对应,但是...

378100
来自专栏计算机视觉战队

在单机上快速、精确的100000类别的检测

今天带来的这篇推送,估计您有读过或试验过,但是为了让更多的科研学者知道这么“牛”的内容知识,接下来就开始说说今天的主题——1000000类的快速精确检测。 注:...

31360
来自专栏程序员互动联盟

算法好等同于编程能力强吗?

算法和编程不是同等而言,学好编程包含层面很多,基础的编程语言,良好的逻辑思维能力(算法算是包含在这个层面),编程最核心的是编程思想。 相比而言算法是编程基础里面...

40050
来自专栏计算机视觉战队

CVPR—II | 经典网络再现,全内容跟踪

今天首先给大家带来“YOLO”!也被上一篇“Faith”读者说对了,在此也感谢大家的关注与阅读,O(∩_∩)O谢谢 YOLO ? 看到这个封面,相信很多很多...

37750
来自专栏MixLab科技+设计实验室

解读:如何让机器自动答题?

冲顶大会、芝士超人、百万赢家、百万英雄……搜狗推语音搜索答题外挂。今天我来总结下利用搜索来答题的技术原理。 本质上,这是一个自动问答( Question Ans...

391100
来自专栏calmound

Farm Irrigation

题意:判断图中的图形有几个集合。         这道题做的郁闷死我了,为了找开始字母的错误一个一个匹对。         这道题让我也懂得了表格的位置可以代表...

28240
来自专栏程序员互动联盟

初学自学编程,从什么语言开始起步比较好?

自学编程如果是兴趣方面的可以选择比较简单的入门语言入手,然后再慢慢切入到新的编程语言,目前相对来说比较好入门的编程语言是python,这门语言的集成度非常高,适...

37950

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励