1016 - Brush (II)
Time Limit: 2 second(s) | Memory Limit: 32 MB |
After the long contest, Samee returned home and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found a brush in his room which has width w. Dusts are defined as 2D points. And since they are scattered everywhere, Samee is a bit confused what to do. So, he attached a rope with the brush such that it can be moved horizontally (in X axis) with the help of the rope but in straight line. He places it anywhere and moves it. For example, the y co-ordinate of the bottom part of the brush is 2 and its width is 3, so the y coordinate of the upper side of the brush will be 5. And if the brush is moved, all dusts whose y co-ordinates are between 2 and 5 (inclusive) will be cleaned. After cleaning all the dusts in that part, Samee places the brush in another place and uses the same procedure. He defined a move as placing the brush in a place and cleaning all the dusts in the horizontal zone of the brush.
You can assume that the rope is sufficiently large. Now Samee wants to clean the room with minimum number of moves. Since he already had a contest, his head is messy. So, help him.
Input
Input starts with an integer T (≤ 15), denoting the number of test cases.
Each case starts with a blank line. The next line contains two integers N (1 ≤ N ≤ 50000) and w (1 ≤ w ≤ 10000), means that there are N dust points. Each of the next N lines will contain two integers: xi yi,denoting coordinates of the dusts. You can assume that (-109 ≤ xi, yi ≤ 109) and all points are distinct.
Output
For each case print the case number and the minimum number of moves.
Sample Input |
Output for Sample Input |
2 3 2 0 0 20 2 30 2 3 1 0 0 20 2 30 2 |
Case 1: 1 Case 2: 2 |
Note
Data set is huge, so use faster I/O methods.
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<string.h>
6 #include<queue>
7 #include<stack>
8 #include<math.h>
9 #include<vector>
10 using namespace std;
11 typedef struct pp
12 {
13 int x;
14 int y;
15 }ss;
16 ss dd[500006];
17 int id[500006];
18 int dp[500006];
19 bool cmp(pp p,pp q)
20 {
21 return p.y<q.y;
22 }
23 int main(void)
24 {
25 int i,j,k;
26 scanf("%d",&k);
27 int s;
28 for(s=1;s<=k;s++)
29 { int n,m;
30 scanf("%d %d",&n,&m);
31 for(i=1;i<=n;i++)
32 {
33 scanf("%d %d",&dd[i].x,&dd[i].y);
34 }
35 sort(dd+1,dd+n+1,cmp);
36 id[0]=0;id[1]=1;
37 for(i=2;i<=n;i++)
38 {
39 int l=0;int r=i;
40 int ik=-1;
41 while(l<=r)
42 {
43 int mid=(l+r)/2;
44 if(dd[mid].y+m>=dd[i].y)
45 {
46 ik=mid;
47 r=mid-1;
48 }
49 else l=mid+1;
50 }
51 id[i]=ik;
52 }
53 fill(dp,dp+500006,1e9);
54 dp[0]=0;
55 for(i=1;i<=n;i++)
56 {
57 dp[i]=dp[id[i]-1]+1;
58 }
59 printf("Case %d: %d\n",s,dp[n]);
60 }
61 return 0;
62 }
最新文章
- HTML5- Canvas入门(二)
- urllib+BeautifulSoup无登录模式爬取豆瓣电影Top250
- HDU4550+贪心
- Java正则表达式的最简单应用
- PHP编写的图片验证码类文件分享方法
- okhttp封装
- Linux内核等待队列
- Sina App Engine(SAE)入门教程(5)- SaeSegment(中文分词服务)使用
- 编写一个循环将list容器的元素逆序输出
- vs运行代码版本不一致删除缓存
- JSON XML IO数据操作
- sublime2 c++的一些使用配置
- 于Unity3D动态创建对象和创建Prefab三种方式的原型对象
- java存放数据的5个地方
- python2用pip进行安装时报错Fatalerrorinlauncher:Unabletocreateprocessusing";
- vue 无限递归级联组件实现方案
- HIT2019春软件构造->;重写hashCode()方法
- 【Algorithm】字符串编辑距离(Levenshtein距离)C++算法实现
- 60.Search Insert Position.md
- 移动端页面:viewport与分辨率的坑