• POJ 1328 Radar Installation 贪心算法

    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

    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

    Source

    #include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define MAXN 1003

/*
对于每个点可以在坐标轴上 得出能覆盖到该点的圆心范围，从而转化为x轴上的很多线段
选取一定数目的点，让所有的线段都包含至少一个点
先按结尾端点排序，然后尽量将雷达分布在右端（这样能尽可能和多个线段重叠）
*/
struct node
{
    double beg,end;
}a[MAXN];
int n,d;
void cal(double x,double y,double &beg,double &end)//要求y<=d
{
    double r = (double)d;
    beg = x - sqrt(r*r-y*y);
    end = x + sqrt(r*r-y*y);
}
bool cmp(node a,node b)
{
    return a.end 

     
  • 相关阅读:
    java毕业设计高校智慧校园学生系统mybatis+源码+调试部署+系统+数据库+lw
    win10桌面便签小工具,安全无广告下载哪一款
    archery安装测试
    Java 协程终于来了，线程即将是过去式？
    ES6 新特性：Class 的继承
    学习笔记 --- RabbitMQ
    小黑准备收拾东西领物资的日常积累：线程与进程
    配置Jedis连接池
    计算机毕业设计Java“华商转转”平台的设计和实现(源码+系统+mysql数据库+lw文档)
    针对从 Apple 购买的 App 或内容申请退款
  • 原文地址：https://blog.csdn.net/m0_72345017/article/details/128010798