#1187. Parking Ships
Parking Ships
【问题描述】
有n(n<=1000)个海盗,每个海盗有一条船,长度为Li(1<=li<=10^9^)。他们的家沿着海边排成一条直线,每一个海盗家的坐标为xi(-10^9^<=xi<=10^9^)。他们会将船也停在海边(船相当于一个闭区间,两两不能相交)。如果某个海盗的船停在家门口(即他家的坐标包含在船所停的区间中),他会很高兴。
有个海盗是老大,他一定要自己的船放在家门口正当中(即他家坐标是他的船的区间中点)。请问怎样安排这些船只停靠才能让最多能让多少的海盗开心呢?
【输入格式】
第1行有一个整数,代表测试数据组数。对于每组测试数据而言包含2行,其中:
第1行有一个整数n,代表海盗的个数。
第2-n行,每行包含两个整数xi和li,含义如题目所述,第一对xi,li即海盗老大的家的坐标和船的长度。
【输出格式】
对每组测试数据,输出一个整数,代表最多能让多少海盗开心。你可以假设海岸是无限长的。
【输入输出样例】
样例输入
2
5
0 6
-5 2
-4 1
4 2
5 3
4
0 4
-5 4
3 4
5 3
样例输出
5
3
Statistics
Related
In following homework: