Radar Installation
Time Limit: 1000MSMemory Limit: 10000K
Total Submissions: 51377Accepted: 11527
思路 ： 每一个岛都在X轴上有一个区间能够被雷达覆盖，x1为可覆盖的左端点，x2为可覆盖的右端点,x1,x2关于岛的X对称。
先对岛以x排序，然后贪心。
将第一个岛的区间 len[ i ].right与其后的岛与区间len[ k ].left比假设前者大则继续与后面的比反之则将区间更新到后者的区间范围 此时ans+1（注意假设有岛屿的区间
len [ k ].right<前者的区间 len[ i ].right 则将区间更新到len[ k ].right） 在继续比下去;
总之就是让雷达在满足当前情况的前提下尽量往右方。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stdlib.h>
using namespace std;
struct Class{
double x;
double y;
}zb[1005];
struct Std{
double s;
double e;
}len[1005];
double r;
int ans,n;
bool cmp(Class a,Class b)
{
return a.x<b.x;
}
void worklen()//将每一个岛屿各自相应的可以放雷达的区域计算出来
{
for(int i=0;i<n;i++)
{
/*cout<<len[i].s<<" "<<len[i].e<<endl;*/
len[i].s=zb[i].x-sqrt(r*r-(zb[i].y*zb[i].y));
len[i].e=zb[i].x+sqrt(r*r-(zb[i].y*zb[i].y));
}
}
void work()
{
int j;
int l=0;
for(j=1;j<n;j++)
{
if(len[j].e<len[l].e)
{
l=j;//当有第j个岛屿雷达的放置区比l个岛屿的小时 注意要把最小的作为比較标准
}
else if(len[l].e<len[j].s)
{
ans++;
l=j;
}
}
return ;
}
int main()
{
int i,flag,t=1;
while(cin>>n>>r,n||r)
{
flag=0;
ans=1;
for(i=0;i<n;i++)
cin>>zb[i].x>>zb[i].y;
for(i=0;i<n;i++)
if(fabs(zb[i].y)>r)
{
flag=1;
}
if(flag)
{
cout<<"Case "<<t<<": "<<"-1"<<endl;
t++;
}
else
{
sort(zb,zb+n,cmp);
/*for(i=0;i<n;i++)
cout<<zb[i].x<<" "<<zb[i].y<<endl;*/
worklen();
work();
cout<<"Case "<<t<<": "<<ans<<endl;
t++;
}
}
return 0;
}