点击打开链接
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 43490 | Accepted: 9640 |
Description
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
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
Sample Input
3 2
1 2
-3 1
2 1 1 2
0 2 0 0
Sample Output
Case 1: 2
Case 2: 1
题目大意就是在X轴上的点是雷达，要用最少的雷达覆盖x轴上部的点（小岛），输入小岛的个数，雷达半径和小岛的坐标，问最少需要多少雷达才能全部覆盖这些小岛
思路1：
我们反过来考虑问题，以每个小岛为圆心，雷达的覆盖范围为半径做一个圆，圆和x轴有一个或者两个交点，那么说明至少在两个交点范围内设置一个雷达才能覆盖到这个小岛，我们可以把两个交点标记为起点和终点，那么对于所有的小岛，都有一个起点和一个终点，然后我们先把这些点按起点排序，选定第一个起点和这个点对应的终点，终点设为E，然后向后选择，如果一个点的起点小于E，而且终点也小于E，那么要把E改写为当前这个点的终点；如果当前点的终点大于E，则不用修改。如果当前点的起点大于E，那么说明需要新建一个雷达以覆盖这个点，计数器加以，终点E重新设置为当前这个点的终点。
#include<stdio.h>
#include<utility>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
int num;
// freopen("test.txt", "r", stdin);
vector<pair<double, double> > v;
for(num = 1; ; num ++)
{
int n, m;
bool f = 0;
scanf("%d %d", &n, &m);
if(n == m && m == 0)
break;
int x, y;
pair<double, double> p;
double dis;
while(n--)
{
scanf("%d %d", &x, &y);
if(y > m)
{
f= 1;
}
dis = sqrt(m * m - y * y);
p.first= x - dis;
p.second = x + dis;
v.push_back(p);
}
if(f == 1)
{
printf("Case %d: -1\n", num);
v.clear();
continue;
}
sort(v.begin(), v.end());
vector<pair<double, double> > ::iterator i;
double tail = v[0].second;
int count = 1;
for(i = v.begin() + 1; i != v.end(); i++)
{
double max = tail;
bool flag = 0;
for(; (*i).first <= tail && i != v.end() ; i++)
{
flag = 1;
if((*i).second < tail)
tail = (*i).second;
}
if(i == v.end())
break; tail = (*i).second;
count ++; }
printf("Case %d: %d\n", num , count);
v.clear();
}
return 0;
}
思路2：今天重新看这个题发现思路1挺乱的，有更简单的思考方式：
以每个小岛为圆心，雷达的覆盖范围为半径做一个圆，圆和x轴有一个或者两个交点，那么说明至少在两个交点范围内设置一个雷达才能覆盖到这个小岛。我们可以把两个交点标记为起点和终点。这样我们就能算出start和end在x轴上的坐标。（这里同思路1）
不同点是：
转换一下题目的描述：
雷达越少越好 == 每个雷达覆盖的小岛数越多越好。
假设我们从左向右安装。
那么选择第一个点的时候第一个end的位置，就是在既能覆盖住第一个点，又能尽量向后覆盖的最后一个位置，这样就能保证覆盖住这个点的同时向后的覆盖面最大。覆盖面更大就更有可能覆盖住后面的点（因为还没有遍历到后面的点，所以后面的点还是未知的），从而实现雷达覆盖的小岛数越多越好这一目标
代码是在思路1的基础上改的，思路1是pair的first是start，second是end，思路二中两个变量换一下（pair自带的排序是先比较第一个）这样就能按end排序了，然后思路就是上面的了：
#include<stdio.h>
#include<utility>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
int num;
vector<pair<double, double> > v;
for(num = 1; ; num ++)
{
int n, m;
bool f = 0;
scanf("%d %d", &n, &m);
if(n == m && m == 0)
break;
int x, y;
pair<double, double> p;
double dis;
while(n--)
{
scanf("%d %d", &x, &y);
if(y > m)
{
f= 1;
}
dis = sqrt(m * m * 1.0 - y * y);
p.second= x - dis;
p.first = x + dis;
v.push_back(p);
}
if(f == 1)
{
printf("Case %d: -1\n", num);
v.clear();
continue;
}
sort(v.begin(), v.end());
vector<pair<double, double> > ::iterator i;
double tail = v[0].first;
int count = 1;
for(i = v.begin() + 1; i != v.end(); i++)
{
if((*i).second > tail)
{
count ++;
tail = (*i).first;
}
}
printf("Case %d: %d\n", num , count);
v.clear();
}
return 0;
}