Description

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.

Figure A Sample Input of Radar Installations

Input

Output

Sample Input

    3 2

1 2

-3 1

2 1



1 2

0 2



0 0


  

Sample Output

    Case 1: 2

Case 2: 1


  

Source

Beijing 2002

題目鏈接： http://poj.org/problem?id=1328

題意：有一條直的海岸線，上面有雷達。以海岸線為x軸，x軸上面為海，下面為岸。海里面有很多島嶼。已知雷達的觀測半徑。問最少建多少個雷達能把所有島嶼都覆蓋到雷達

?????????? 的偵測范圍內。如果不能覆蓋全部的島嶼，按樣例輸出Case數和-1，反之輸出Case數和最少需要建立的雷達數。

分析：首先算出經過每個雷達且平行于x軸的弦：假設雷達覆蓋半徑為d。則弦的左端點為x-sqrt (d*d-y*y),右端點為x+sqrt(d*d-y*y)。然后按左端點從小到大排序。由于不能受右

?????????? 端點的影響，將弦的左右端點橫坐標用結構體存起來。然后，將第一個雷達放在排序后的弦投影在x軸的右端點temp。從過第2個島嶼的弦的投影開始掃描，如果右端點

?????????? <temp即右端點在雷達左邊。把雷達移動到此右端點，此時就能使雷達既覆蓋到這個島嶼，又覆蓋到前面的島嶼。如果左端點在雷達右邊，則不能覆蓋，需要再建立一個

??????????? 雷達。然后把新雷達建在此時弦右端點投影到x軸的坐標。忽略前面的，對后面的島嶼進行同樣的操作。（貪心思想）

注意：半徑和坐標都有可能是小數，所以用double類型比較好，不然用int又要注意計算時*1.000變為浮點數。

代碼：

    #include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;



struct point

{

    double left;

    double right;

}p[5012];

bool flag;

int cnt;



bool cmp(point &x,point &y)

{

    return x.left<y.left;

}



int main()

{

    int cases=0,i,n;

    double d;

    while(scanf("%d%lf",&n,&d)&&n&&d)

    {

        flag=true;

        double a,b;

        for(i=0;i<n;i++)

        {

            scanf("%lf%lf",&a,&b);

            if(fabs(b)>d)

	    flag=false;

            p[i].left=a-sqrt(d*d-b*b);

            p[i].right=a+sqrt(d*d-b*b);

        }

	printf("Case %d: ",++cases);

	if(!flag)

	    puts("-1");

	else

	{

	    sort(p,p+n,cmp);

	    double temp=p[0].right;

	    cnt=1;

	    for(i=1;i<n;i++)

	    {

		if(p[i].right<temp)

		   temp=p[i].right;

		else if(p[i].left>temp)

	        {

		   cnt++;

		   temp=p[i].right;

		}

	    } 

	    printf("%d\n",cnt);

	}

    }

    return 0;

}





//AC
  

?

?

?

?

?

?

poj 1328 Radar Installation (簡單的貪心)