ZOJ-1360 || POJ-1328——Radar Installation
2024-09-08 03:57:57
ZOJ地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=360
POJ地址：http://poj.org/problem?id=1328
解题思路：贪心
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4 #include <math.h>
5
6 struct P{
7 double x, y, left, right;
8 }p[];
9
int cmp(const void *a, const void *b){
struct P *c = (struct P *)a;
struct P *d = (struct P *)b;
return c->left > d->left ? : -;
}
int main(){
int n, i, j, r, ans, lose, Case = ;
double d, x, dis, high;
while(scanf("%d %d", &n, &r) != EOF){
if(n == && r == ){
break;
}
lose = ;
d = (double)r;
for(i = ; i < n; i++){
scanf("%lf %lf", &p[i].x, &p[i].y);
if(p[i].y > d){ //如果某个点的y左边大于雷达半径，那么一定无法覆盖
lose = ;
}
dis = sqrt(d * d - p[i].y * p[i].y);
p[i].left = p[i].x - dis;
p[i].right = p[i].x + dis;
}
if(lose == ){
printf("Case %d: -1\n", Case++);
continue;
}
qsort(p, n, sizeof(p[]), cmp);
ans = ;
high = p[].right; //令第一个点的右端点为最远点
for(i = ; i < n; i++){
if(p[i].left <= high){
high = p[i].right < high ? p[i].right : high;//如果该点的左端点在最远点内，更新最远点
}
else{ //如果左端点不在最远点内，雷达数+1，更新最远点
ans++;
high = p[i].right;
}
}
printf("Case %d: %d\n", Case++, ans);
}
return ;
53 }
最新文章
- (4)Redis 资料
- STM32之RTC配置与初始化-rtc.h rtc.c
- NSBlockOperation添加多个任务
- HTML5要点（二）
- SQL Server重建索引计划
- JavaScript判断数据类型总结
- char * 和 void *
- HTTP 503 错误 – 服务不可用 (Service unavailable)
- Silk Mobile – 缩短移动应用的测试周期
- cocos2dx的runAction: 反复运行,多个动作连接运行,多个动作同一时候运行的实现
- 网页html结构搭建方法总结
- react小结
- 2.10 while循环应用
- ActionFilterAttribute 全局记录API日志
- MySQL添加列、删除列，创建主键等常用操作总结
- mybatis的三种批量插入以及次效率比较
- 论坛IP地址追踪&路由器密码嗅探
- 词云绘制wordcloud
- linux基本介绍和使用
- Could not allocate 40960 bytes percpu data