| 题目名称 | 1777. [国家集训队2012]Bomb |
|---|---|
| 输入输出 | nt2012_bomb.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 4000 ms (4 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-10-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：6， 通过率：16.67% | ||||
 MiracleEEEE |
100 | 0.581 s | 1.84 MiB | C++ |
|
MiracleEEEE |
35 | 29.318 s | 1.84 MiB | C++ |
 石家庄二中教练 |
30 | 0.285 s | 4.14 MiB | C++ |
|
MiracleEEEE |
10 | 29.303 s | 1.84 MiB | C++ |
 Satoshi |
0 | 12.502 s | 4.14 MiB | C++ |
|
Satoshi |
0 | 29.466 s | 4.14 MiB | C++ |
| 关于 Bomb 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
看不懂曼哈顿距离的路过。。。
 Hzoi_
2016-02-15 13:52
1楼
| ||||
Bomb(李超)
时间限制：4.0s 内存限制：512.0MB
【试题来源】
2012集训队互测-李超
【问题描述】
A国和B国是两个超级大国，长期处于冷战状态；
A国在B国中设有N个情报站，编号为1,2,3,……,N，每个情报站有一个坐标(Xi,Yi)。
但是，A国的工作人员发现，每个情报站里都被埋上了炸弹！
这些炸弹非常特殊，只要同时拆除其中的三个炸弹，所有炸弹就都不会爆炸了。
由于各个情报站联络需要代价，拆除炸弹需要花费的总代价为这些炸弹两两之间的曼哈顿距离和。
现在A国的指挥部门找到了你，希望知道可能需要的最大代价和最小代价。
A国在B国中设有N个情报站，编号为1,2,3,……,N，每个情报站有一个坐标(Xi,Yi)。
但是，A国的工作人员发现，每个情报站里都被埋上了炸弹！
这些炸弹非常特殊，只要同时拆除其中的三个炸弹，所有炸弹就都不会爆炸了。
由于各个情报站联络需要代价，拆除炸弹需要花费的总代价为这些炸弹两两之间的曼哈顿距离和。
现在A国的指挥部门找到了你，希望知道可能需要的最大代价和最小代价。
【输入格式】
输入的第一行包含一个整数N。接下来N行，第i+1行两个整数Xi,Yi，表示第i个情报站的坐标。
【输出格式】
输出两行，每行包含一个整数，第一行表示可能的最大代价，第二行表示可能的最小代价。
【样例输入】
4
1 1
1 2
2 1
2 3
1 1
1 2
2 1
2 3
【样例输出】
6
4
4
【数据规模和约定】
对于30%的数据，N<=500
对于另外10%的数据，每个点出现至少两遍
对于50%的数据，N<=1000
对于60%的数据，N<=8000
对于70%的数据，N<=15000
对于80%的数据，N<=50000
对于100%的数据，N<=100000，0<=Xi,Yi<=10^8
对于另外10%的数据，每个点出现至少两遍
对于50%的数据，N<=1000
对于60%的数据，N<=8000
对于70%的数据，N<=15000
对于80%的数据，N<=50000
对于100%的数据，N<=100000，0<=Xi,Yi<=10^8
【注释】
对于两个点(X0,Y0),(X1,Y1)，
它们之间的曼哈顿距离为abs(X0-X1)+abs(Y0-Y1)。
其中abs(x)表示x的绝对值。
它们之间的曼哈顿距离为abs(X0-X1)+abs(Y0-Y1)。
其中abs(x)表示x的绝对值。