当前位置: 首页 > 工具软件 > Cottage > 使用案例 >

CodeForces 15A-Cottage Village(思维题)

裴兴言
2023-12-01

A new cottage village called «Flatville» is being built in Flatland. By now they have already built in «Flatville» n square houses with the centres on the Оx-axis. The houses’ sides are parallel to the coordinate axes. It’s known that no two houses overlap, but they can touch each other.

The architect bureau, where Peter works, was commissioned to build a new house in «Flatville». The customer wants his future house to be on the Оx-axis, to be square in shape, have a side t, and touch at least one of the already built houses. For sure, its sides should be parallel to the coordinate axes, its centre should be on the Ox-axis and it shouldn’t overlap any of the houses in the village.

Peter was given a list of all the houses in «Flatville». Would you help him find the amount of possible positions of the new house?

Input

The first line of the input data contains numbers n and t (1 ≤ n, t ≤ 1000). Then there follow n lines, each of them contains two space-separated integer numbers: xi ai, where xi — x-coordinate of the centre of the i-th house, and ai — length of its side ( - 1000 ≤ xi ≤ 1000, 1 ≤ ai ≤ 1000).

Output

Output the amount of possible positions of the new house.

Examples

Input

2 2
0 4
6 2

Output

4

Input

2 2
0 4
5 2

Output

3

Input

2 3
0 4
5 2

Output

2

Note

It is possible for the x-coordinate of the new house to have non-integer value.

Flatland正在建造一个名为“ Flatville”的新平房村。到目前为止,他们已经建造了«Flatville»n方形房屋,中心位于Оx轴上。房屋的侧面与坐标轴平行。众所周知,没有两座房子重叠,但它们可以相互接触。

彼得工作的建筑师局受命在“弗拉特维尔”建造新房。客户希望他的未来房屋在Оx轴上,呈正方形,侧面为t,并且至少接触一栋已建成的房屋。当然,其侧面应与坐标轴平行,其中心应在Ox轴上,并且不应与村庄中的任何房屋重叠。

彼得得到了“弗拉特维尔”所有房屋的清单。您能帮他找到新房子的可能位置吗?

输入值
输入数据的第一行包含数字n和t(1≤n,t≤1000)。然后是n行,每行包含两个以空格分隔的整数:xi ai,其中xi-第i个房屋的中心的x坐标,ai-边的长度(-1000≤xi≤1000 ,1≤ai≤1000)。

输出量
输出新房子的可能位置数量。

例子
输入值
2 2
0 4
6 2
输出量
4
输入值
2 2
0 4
5 2
输出量
3
输入值
2 3
0 4
5 2
输出量
2
注意
新房子的x坐标可能具有非整数值。

这道题是CF上的,也是一道思维题,读懂题意后会发现很好做,题目的意思是在一些房子已经建好的情况下,再建一座边长为t的房子,求可能的所有位置,题目有很多细节,比如题目没有说明 t 一定是整数,题目也没有说明路的范围是无限大的(因为这两个点WA了好几次),我们依次读入xi和ai,然后根据xi把这些房子排好序,我们计算两个房子中间的间隔,如果大于 t 则说明中间有两个可能的位置可以建房子,如果等于 t 则说明只有一个位置,如果小于 t 则说明没有位置可以建房子,因为路是无限大的,所以在首尾也能建房子,最后ans+=2,输出ans即可。AC代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int _max=1e3+50;
struct node {double xi,ai;};//不定义double 会wa
struct node a[_max];
bool cmp(node a,node b)
{
	return a.xi<b.xi;
}
int main()
{
	ios::sync_with_stdio(false);
	int n;
	double t;
	cin>>n>>t;
	int ans=0;
	for(int i=0;i<n;i++)
	  cin>>a[i].xi>>a[i].ai;
	sort(a,a+n,cmp);//根据xi排序
	for(int i=1;i<n;i++)
	  if(((a[i].xi-a[i].ai/2)-(a[i-1].xi+a[i-1].ai/2))>t)//判断房子与房子之间的间隔
	    ans+=2;
	  else if(((a[i].xi-a[i].ai/2)-(a[i-1].xi+a[i-1].ai/2))==t)
	    ans++;
	ans+=2;//最后ans++
	cout<<ans<<endl;
	return 0;
}
 类似资料: