本帖最后由 勿语静候 于 2014-7-25 08:46 编辑 #include<iostream>
#include<vector>
#include<cmath>
using namespace std;
struct island{
double x;
double y;
double distance;
double t = pow((distance * distance - y * y),0.5);
double start = ceil(x - t);
double end = floor(x + t);
};
void sort(double *start,int landNum)//用雷达区间起始点排序岛屿
{
for(int i = landNum - 1;i > 0;i--)
{
if(start[i] < start[i - 1])
{
double temp = start[i - 1];
start[i - 1] = start[i];
start[i] = temp;
}
}
}
//size是已经存入容器中岛屿个数
//a[]是已经存入岛屿的结束点
//start是当前岛屿起始点
int test(int size ,double* a,double start)
{
int flag = 1;
for(int i = 0;i < size;i++)
{
if(start <= a[i])
flag = 0;
}
return flag;
}
int main()
{
//input
int islandNum;
double radarDistance;
int d = 1;
while (cin >> islandNum >> radarDistance&&(islandNum || radarDistance))
{
island island[islandNum];
for(int i = 0;i < islandNum;i++)
{
cin >> island[i].x >> island[i].y;
island[i].distance = radarDistance;
}
double start1[islandNum];//存储所有岛屿的雷达区间起始点
for(int i = 0;i < islandNum;i++)
{
start1[i] = island[i].start;
}
sort(start1,islandNum);
vector<int> islandSubcript;//存储被选中雷达的岛屿下标
islandSubcript.push_back(0);//第一个岛屿必然被选中
for(int i = 1;i < islandNum;i++)
{
//比较当前第i+1岛屿与之前所有岛屿的结束点,若符合加入容器
double a[islandSubcript.size()];//存储所有岛屿结束点
for(int j = 0;j < islandSubcript.size();j++)
{
a[j] = island[j].end;
}
double s = island[i].start;
if(test(islandSubcript.size(),a,s))
{
islandSubcript.push_back(i);
}
}
cout << "Case " << d++<<": " <<islandSubcript.size()<<endl;
}
return 0;
}
|