昆明建设局官方网站,网站快速备案多少钱,赣州人才网官网入口,网站是用什么软件做的Radar Installation
poj 1328
题目大意#xff1a;
在平面直角坐标系的一二象限上有n个小岛#xff0c;现在让你在x坐标上布置雷达#xff0c;每个雷达可以侦测以它为原心#xff0c;半径为m的圆内的所有小岛#xff0c;现在问侦测完这n个小岛最少要多少个雷达
输入样…Radar Installation
poj 1328
题目大意
在平面直角坐标系的一二象限上有n个小岛现在让你在x坐标上布置雷达每个雷达可以侦测以它为原心半径为m的圆内的所有小岛现在问侦测完这n个小岛最少要多少个雷达
输入样例
3 2
1 2
-3 1
2 11 2
0 20 0输出样例
Case 1: 2
Case 2: 1数据范围
1⩽n⩽10001\leqslant n\leqslant 10001⩽n⩽1000
解题思路
把每个点可以被哪个范围内雷达侦测到记录下来然后按范围的最尾端从小到大排序然后每一次在需要安装雷达的范围的最右端安装雷达这样可以让更多的点被侦测到
代码
#includecmath
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
int n,t,pp,ans;
double x,y,m,k;
struct rec
{double bg,ed;
}a[1500];
bool cmp(rec x,rec y){return x.edy.ed||x.edy.edx.bgy.bg;}
int main()
{scanf(%d %lf,n,m);while(n){t;pp0;for (int i1;in;i){scanf(%lf %lf,x,y);if (ym) pp1;a[i].bgx-sqrt(m*m-y*y);//计算范围a[i].edxsqrt(m*m-y*y);}if (pp)//离x轴的坐标大于m则无解{printf(Case %d: -1\n,t);scanf(%d %lf,n,m);continue;}sort(a1,a1n,cmp);//排序ans1;ka[1].ed;//最后面的雷达for (int i2;in;i)if (a[i].bgk)//没有被侦测到ans,ka[i].ed;//新建一个printf(Case %d: %d\n,t,ans);scanf(%d %lf,n,m);}
}
