ny偶就287 Radar

梦里梦外; 2022-04-03 14:08 159阅读 0赞

## Radar ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 3

描述

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.

![20110505064233_82697.jpg][]

输入

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.  
  
The input is terminated by a line containing pair of zeros

输出

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

解题思路：  
此题意思给定点集S=\{（xi，yi）i=1.2.3...n\}，求用圆心在x轴上，半径为d的圆覆盖S所需的圆的最少个数。  
1.先把给出的岛的坐标（xi.yi）和半径r转化为在x轴上的区间，即当d-yi>=0时，圆心位于x轴上的区间为Ii=\[ xi-sqrt(d^2-yi^2) , xi + sqrt( d^2 - yi^2 )\],则转化为区间选点问题。  
2.S中点（xi，yi），对应一个在x轴上的区间Ii=（li，ri），按照区间右端点ri从小到大排序，在区间集合中选择一个索引最小的区间，把选择的区间和与其相交的所有区间作为一组从T中删除，直到T为空集、  
3则剩下的分组的组数即为m的最小值、、、

//正确代码，结构严密，逻辑性强、以后逐渐养成好习惯。

\#include<stdio.h>  
\#include<stdlib.h>  
\#include<math.h>  
  
  
const double EPS=1e-8; //误差精度  
const int N=1200;  
struct Node  
\{  
float a,b;  
\};  
int cmp(const void\* a,const void\* b) //按照右端点从小到大  
\{  
return (\*(Node \*)a).b>(\*(Node \*)b).b;  
\}  
Node ss\[N\];  
float xi,yi;  
bool covered\[N\];  
  
  
int main()  
\{  
int t,n,d,i,j,count;  
bool nosol;  
t=0;  
while(scanf("%d %d",&n,&d) && !(n==0&&d==0))  
\{  
t++;  
nosol=false;  
if(d<=0) nosol=true;  
for(i=0;i<n;i++)  
\{  
scanf("%f%f",&xi,&yi);  
if(!nosol)  
\{  
if(yi>d) nosol=true;  
else  
\{  
float dx=sqrt(d\*d - yi\*yi);  
ss\[i\].a = xi - dx;  
ss\[i\].b = xi + dx;  
\}  
\}  
\}  
if(nosol) \{printf("Case %d: -1\\n",t);\}  
else  
\{  
//初始化各个笑道未被覆盖  
for(i=0;i<n;i++)  
\{ covered\[i\]=false;\}  
count=0;  
  
  
qsort(ss,n,sizeof(ss\[0\]),cmp);  
// for(i=0;i<n;i++)  
// printf("%f %f\\n",ss\[i\].a,ss\[i\].b);  
for(i=0;i<n;i++) //贪心求解  
\{  
if(!covered\[i\])  
\{  
count++; covered\[i\]=true;  
for(j=i+1;j<n;j++) //删除相交区域  
\{  
if(ss\[j\].a <= ss\[i\].b)  
covered\[j\]=true;  
\}  
\}  
\}  
printf("Case %d: %d\\n",t,count);  
\}  
  
  
\}  
return 0;  
\}

//看看怎么错了、wa。。。  
  
\#include<stdio.h>  
\#include<stdlib.h>  
\#include<math.h>  
  
  
struct Node  
\{  
float a,b;  
\};  
int cmp(const void\* a,const void\* b) //按照右端点从小到大  
\{  
return (\*(Node \*)a).b>(\*(Node \*)b).b;  
\}  
Node ss\[1200\];  
int aa\[1200\],bb\[1200\];  
bool covered\[1200\];  
int main()  
\{  
int t,n,d,i,j,count;  
t=1;  
while(scanf("%d %d",&n,&d) && !(n==0&&d==0))  
\{  
for(i=0;i<n;i++)  
scanf("%d%d",&aa\[i\],&bb\[i\]);  
for(i=0;i<n;i++)  
\{  
if(d-bb\[i\]<0) \{break; \}  
else  
\{  
ss\[i\].a = aa\[i\] - sqrt(d\*d-bb\[i\]\*bb\[i\]);  
ss\[i\].b = aa\[i\] + sqrt(d\*d-bb\[i\]\*bb\[i\]);  
\}  
\}  
if(d-bb\[i\]<0||d<=0) \{printf("Case %d: -1\\n",t);\}  
else  
\{  
//初始化各个笑道未被覆盖  
for(i=0;i<n;i++)  
\{ covered\[i\]=false;\}  
count=0;  
  
  
qsort(ss,n,sizeof(ss\[0\]),cmp);  
// for(i=0;i<n;i++)  
// printf("%f %f\\n",ss\[i\].a,ss\[i\].b);  
for(i=0;i<n;i++) //贪心求解  
\{  
if(!covered\[i\])  
\{  
count++; covered\[i\]=true;  
for(j=i+1;j<n;j++) //删除相交区域  
\{  
if(ss\[j\].a <= ss\[i\].b)  
covered\[j\]=true;  
\}  
\}  
\}  
printf("Case %d: %d\\n",t,count);  
\}  
t++;  
\}  
return 0;  
\}

[20110505064233_82697.jpg]: http://acm.nyist.net/JudgeOnline/admin/kind/attached/20110505064233_82697.jpg