注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 1328 Radar Installation 贪心  

2011-04-22 10:30:27|  分类: 贪心 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://poj.org/problem?id=1328
X轴的上方代表海,下方代表陆地。海中有多个岛屿,X轴上可任意放置半径为d的雷达,求至少放置多少个雷达可覆盖所有岛屿,不能完成输出-1。
    以岛屿为圆心做半径为d的圆,可在X轴上产生两个交点,即为X轴上可覆盖该岛屿的区间,求出所有岛屿所对应的区间,将交集不为空的区间分为一组,这样你会发现答案其实就是求区间可分为多少组。
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
struct point
{
       double x,y;
}p[1005];
struct in
{
      double l,r;
}q[1005];
int cmp(in a,in b)
{
    if(a.l-b.l<-1e-8)
    return 1;
    else
    return 0;
}
double dis(point a,point b)
{
       return sqrt(a.x*a.x+b.y*b.y);
}
int main()
{
    int i,j,ans,n,d,flag,cas=1;
    double x,a,b;
    while(scanf("%d%d",&n,&d),n+d)
    {
         flag=0;ans=1;
         for(i=0;i<n;i++)
         {
              scanf("%lf%lf",&p[i].x,&p[i].y);
              if(p[i].y>d)
              flag=1;
         }
         if(flag)
         {
              printf("Case %d: -1\n",cas++);
              continue;
         }
         for(i=0;i<n;i++)
         {
              q[i].l=p[i].x-sqrt(d*d-p[i].y*p[i].y);
              q[i].r=sqrt(d*d-p[i].y*p[i].y)+p[i].x;
         }           //求解每个区间。
         sort(q,q+n,cmp);   //每个区间以左端点大小,从小到大排序。
         a=q[0].l;b=q[0].r;
         for(i=1;i<n;i++)
         {
              if(q[i].l>b)
              {
                   ans++;
                   a=q[i].l;
                   b=q[i].r;
              }
              else if(q[i].l<=b)
              {
                   a=q[i].l;
                   if(q[i].r<b)
                   b=q[i].r;
              }
         }
         printf("Case %d: %d\n",cas++,ans);
         
    }
    return 0;
}
         
         
              
  评论这张
 
阅读(146)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018