codefroces 650A. Watchmen
3 seconds
256 megabytes
standard input
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.
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.
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.
3
1 1
7 5
1 5
2
6
0 0
0 1
0 2
-1 1
0 1
1 1
11
In the first sample, the distance between watchman 1 and watchman 2 is equal to |1 - 7| + |1 - 5| = 10 for Doctor Manhattan and for Daniel. For pairs (1, 1), (1, 5) and (7, 5), (1, 5) Doctor Manhattan and Daniel will calculate the same distances.
加上相同的,减去重复的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
map<ll,ll>ans,pos;
map<pair<ll,ll>,ll>inf;
ll x,y,n,cnt=;
cin>>n;
while(n--)
{
cin>>x>>y;
cnt+=ans[x]++;
cnt+=pos[y]++;
cnt-=inf[make_pair(x,y)]++;//减去重复的
}
cout<<cnt<<endl;
}
最新文章
- 自适应备忘录 demo
- go语言学习笔记
- CXF调用webservice超时设置
- struts2 的正则表达式验证不起作用解决办法
- 11-10 CC150第一章
- loj 1165(bfs+康托展开)
- HDU 1533 &; KM模板
- 【开发记录】iOS中使用 Reachability 检测网络
- [resource]23个python的机器学习包
- Android Fragment基础及使用
- 基于visual Studio2013解决C语言竞赛题之0907删除记录
- unix网络编程环境搭建
- Hangfire源码解析-如何实现可扩展IOC的?
- 遍历文件后缀名 为 .java的文件
- Blender学习笔记
- 【Bcftools】合并不同sample的vcf文件,通过bcftools
- JavaEE编程实验 实验1 Java常用工具类编程(未完成)
- JS中";属性";的用法
- Redis基本数据类型命令汇总
- 洛咕 P3321 [SDOI2015]序列统计