ACM题解——贪心——卫星安装_贪心算法与卫星结合

ACM题解——贪心——卫星安装转化类似节目安排问题

题目描述

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

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

 

Output

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.

 

Sample Input

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Sample Output

Case 1: 2
Case 2: 1

题意

现在有n个点，给定n个位置（xi，yi）(均>=0)，有半径为r的卫星安装在x轴上，想要所有卫星的辐射范围囊括所有位置，求最少的卫星个数。

题解

一开始我想的是将岛屿按照x轴大小排序，然后for循环遍历，y轴大于半径直接让标记值为1，跳出循环，输出-1；如果不是就让这个点压在一个半圆的最左边，求圆心，以致包括右边更多的点，这个圆心传递下去；遍历第二个坐标依次判断y轴是不是大于半径，然后查看该点坐标在不在以传递圆心为圆心的半圆内，若在传递圆心不变，要不在，就让这个点做新圆心的边界最左，然后求新的圆心值，并且卫星个数++；最后遍历完所有位置，输出卫星个数即可。

但是wa了，以上坐标我虽然都用了double来算，但是不排除有小数取了整造成的偏移错误。于是考虑换一个算法：

对每一个位置，确定可以满足囊括这个位置的圆心范围，x1，x2,   $x_1=x-\sqrt{r^{2}-y^{2}}$    $x_2=x+\sqrt{r^{2}-y^{2}}$,将每一个位置的圆心范围放入结构体，按照右范围（注意一定是按右范围进行排序）从小到大排序，记录当前右范围curr；循环遍历每一个位置的左右范围，若左范围<=curr,则不做处理，若>curr，则更新curr为当前右范围，且卫星计数器++；最终遍历完所有位置之后输出计数器的值即可。

代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct point
{
    long double x;
    long double y;
    long double l;   //记录岛屿 圆心左范围
    long double r;   //        圆心右范围
};
bool cmp(point a,point b)
{
    return a.r<b.r;
}
int main()
{
    int n=0;
    double k=0;
    cin>>n>>k;
    long long int num=0;
    while(n!=0 || k!=0)
    {
        num++;
        point *p=new point[n];
        bool flag=0;
        for(int i=0;i<n;i++)
        {
            cin>>p[i].x>>p[i].y;
            p[i].l=p[i].x-sqrt(k*k-p[i].y*p[i].y);
            p[i].r=p[i].x+sqrt(k*k-p[i].y*p[i].y);
            if(p[i].y>k)
                flag=1;
        }
        if(flag==1)
            cout<<"Case "<<num<<": "<<"-1"<<endl;  //先排除有y大于r的可能
        else
        {
            sort(p,p+n,cmp);    
            long long int coun=1;
            long double index=p[0].r;
            for(int i=1;i<n;i++)
            {
                if(p[i].l>index)
                {
                    coun++;
                    index=p[i].r;
                }
            }
            cout<<"Case "<<num<<": "<<coun<<endl;
        }
        cin>>n>>k;
    }
    return 0;
}