Codeforces 651 C. 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.
题意就是曼哈顿距离和欧几里得距离,自己把公式随便算一算就得出要在同一个横坐标或者是同一个纵坐标的才成立,然后就可以用握手问题的那个公式,再把重复的相同的位置去掉就可以。
然而握手问题的公式我不会写。。。所以想了一个其他的,代码看一下就会懂的。。。
要用long long。。。
然后就是排序的时候要注意!!!别写错了==,wa在排序写错了。。。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=2*1e7;
typedef long long ll;
struct node{
int a,b;
}dis[N];
bool cmp1(node x,node y){
if(x.a==y.a)
return x.b<y.b;
return x.a<y.a;
}
bool cmp2(node x,node y){
if(x.b==y.b)
return x.a<y.a;
return x.b<y.b;
}
int main(){
int n;
ll cnt,ans;
while(~scanf("%d",&n)){
for(int i=0;i<n;i++)
scanf("%I64d%I64d",&dis[i].a,&dis[i].b);
sort(dis,dis+n,cmp1);
cnt=0;ans=0;
for(int i=1;i<n;i++){
if(dis[i].a==dis[cnt].a)
ans+=abs(i-cnt);
else
cnt=i;
}
cnt=0;
sort(dis,dis+n,cmp2);
for(int i=1;i<n;i++){
if(dis[i].b==dis[cnt].b)
ans+=abs(i-cnt);
else
cnt=i;
}
cnt=0;
for(int i=1;i<n;i++){
if(dis[i].a==dis[cnt].a&&dis[i].b==dis[cnt].b)
ans-=abs(i-cnt);
else
cnt=i;
}
printf("%I64d\n",ans);
}
return 0;
}
最新文章
- Spring 4 异常处理
- springMVC 的工作原理和机制(转)
- c#新手之1-如何组织类及相互调用
- Spring 框架 详解 (二)
- c/c++----网站及其后门(CGI应用程序)
- mybatis系列-14-延迟加载
- Code Forces 448C Painting Fence 贪婪的递归
- TCP的核心系列 — ACK的处理(一)
- RabbitMQ 消息确认机制以及lazy queue+ disk消息持久化
- Ubuntu操作用户账户
- C语言malloc函数为一维,二维,三维数组分配空间
- SQL Server 主库DML操作慢故障处理过程
- Hibernate中Restrictions查询用法(转)
- kafka学习总结之kafka核心
- 常用AT指令集 (转)
- 提高Intellij创建Maven工程的速度
- aarch64_n3
- React with webpack - part 1
- HDU - 2087 求不可重复字符串的匹配次数
- 【Spring实战】—— 13 AspectJ注解切面
热门文章
- hdu 1207 汉诺塔II (DP+递推)
- 左侧导航条+中间显示内容+右侧菜单配置,Bootstrap+AdminLTE+Jquery
- linux kernel 关于RSS/RPS/RFS/XPS的介绍
- eclipse集成mybatis的generater插件
- 买卖股票的最佳时机 [ leetcode ]
- socket编程 ------ BSD socket API
- TOM的show_space
- 群联MPALL(Rel) 7F V5.03.0A-DL07量产工具 PS2251-07(PS2307)
- MyBatis的SQL语句映射文件详解(三)----多参数传递的几种方式
- 通俗解释IOC原理