|
/*思路一：先考虑y=d的情况，吧涉及到的点标记，然后再从左到右扫描，让尽可能多的点在一个圆内
，复杂度O(n^2)
**********有错误呀，昨晚检查了一晚上还没检查出开呀******！！！！
，据说渣哥去年都AC了，膜拜呀，要被他鄙视了*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
struct node {
int x,y;
bool flag;
}array[1010];
int cmp(const void *a,const void *b)//int cmp(node *a,node *b)
{ //{ return a.x-b.x;}
return ((struct node*)a)->x -((struct node*)b)->x;
}
int main()
{
int n,d,cnt=0;
while(scanf("%d %d",&n,&d)!=EOF)
{
if(n==0&&d==0)break;
cnt++;
int i,j,sum=0;
double temp;
bool flag=false;
for(i=0;i<n;i++)
{
scanf("%d %d",&array[i].x,&array[i].y);
array[i].flag=false;
if(array[i].y>d)
{cout<<"-1"<<endl; flag=true;}
}
if(flag) continue;
qsort(array,n,sizeof(array[0]),cmp);//sort(array,array+n,cmp)
for(i=0;i<n;i++)
{
if(array[i].y==d)//?????????????
{
sum++;
array[i].flag=true;
for(j=0;j!=i&&j<n;j++)
if((array[j].x-array[i].x)*(array[j].x-
array[i].x)+array[j].y*array[j].y<=d*d)
{array[j].flag=true;
cout<<array[j].flag<<"***"<<endl;
}
}
}
for(i=0;i<n;i++)
{
if(array[i].flag==true) continue;
sum++;
array[i].flag=true;
for(j=i+1;j<n;j++)
{
if(array[j].flag==true)continue;
else
{
temp=(array[i].x-array[j].x)*
(array[i].x-array[j].x)+array[j].y*array[j].y
-2*fabs((array[i].x-array[j].x)*1.0)*
sqrt((d*d-array[i].y*array[i].y)*1.0)
+array[j].y*array[j].y-2*d*d;
if(temp<=0)
{
array[j].flag=true;
}
else
{ break; }
}
}
}//*****for
printf("Case %d: %d\n",cnt,sum);
}
return 0;
}*/
/*思路二：（在网上百度的，牛人呀，复杂度O（nlogn））
题目大意：在一条水平线之上有许多岛屿，在其之下是陆地，现在要在水平线上安装一些雷达（同时给你雷达能够覆盖的区域），让所有的岛屿都可以被雷达覆盖，求能够满足要求的雷达的最少数量，当有的岛屿不能覆盖时输出-1。 做题思路：以每个岛屿为中心，给定的半径为半径画圆，有三种情况出现，与水平线有一个交点，有两个节点，没有交点（这种情况输出数出负一即可）前两种情况可以归为一类，既有交点。最后在水平线上会有许多区域，有的区域重合，这时在重合的地方放一个雷达可以同时覆盖多个区域。可以以每组的左交点为基准由小到大排序，这样以第一个的左端点对应的右端点为起始右端点，当下一个重叠区域的右交点小于右端点，更新右端点为现在的右交点，当下一个的左交点大于当前的右端点是雷达树量加一重复以前几步即可。注意本题雷达被放的位置可能不为整数，所以可以定义有关的变量为double型即可。 注意给的测试数据半径可能有负的同时岛屿有在陆地的情况，这两种情况都输出-1.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
struct node{
double l,r;
}segment[1010];
int cmp(node a,node b)
{
return a.l<b.l;//(a.l-b.l)>0?1:-1;
}
int main()
{
int n,d,cnt=0;
while(scanf("%d %d",&n,&d)!=EOF)
{
if(n==0&&d==0) break;
double x,y,temp;
int sum=0,i;
bool flag=false;
cnt++;
for(i=0;i<n;i++)
{
scanf("%lf %lf",&x,&y);
if(y>d)
{flag=true;}
segment[i].l=x*1.0-sqrt(d*d*1.0-y*y);
segment[i].r=x*1.0+sqrt(d*d*1.0-y*y);
}
sort(segment,segment+n,cmp);
temp=segment[0].r;
sum++;
for(i=1;i<n;i++)
{/*************************
if(i==0)
{
sum++;
x=segment[i].l;
y=segment[i].r;
}
else
{
if(segment[i].r<=y)
{
x=segment[i].l;
y=segment[i].r;
}
else if(segment[i].l>x&&segment[i].r>y)
{
x=segment[i].l;
}
else
{
sum++;
x=segment[i].l;
y=segment[i].r;
}
}**********************/
if(segment[i].l>temp)
{
sum++;
temp=segment[i].r;
}
else if(segment[i].r<temp)
temp=segment[i].r;
}//*****for
if(flag==true)
printf("Case %d: -1\n",cnt);
else
printf("Case %d: %d\n",cnt,sum);
}
return 0;
}
|