Toggle navigation
HUSTOJ
F.A.Qs
ProblemSet
Source/Category
Status
Ranklist
Contest
Login
Problem4474--修剪树木
4474: 修剪树木
Time Limit:
1
Sec
Memory Limit:
128 MB
Submit:
0
Solved:
0
[
Status
] [
Submit
] [Creator:
]
Description
一条水平的马路上种了n棵树,过了几年树都长得很高大了,由于有的树过于高大,挡住了其他的树,使得另一些树得不到阳光。如果有两棵树i、j,i顶端与j底端连线的倾角大于45度,我们就定义为i挡住了j。现在望将一些树砍低,使得不存在挡住的情况。他想知道总共最少需要砍掉多少长度,请你来帮他计算一下。
Input
第一行一个正整数n,表示有n棵树。
接下来n行,每行两个正整数p[i],h[i],表示一棵树的位置和高度。
Output
输出一个数,表示最少砍断多少长度。
Sample Input
Copy
3 0 2 1 2 3 3
Sample Output
Copy
3
HINT
N<=1000
Source/Category
140_T04'