| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 791 人关注过本帖
标题:问一个关于区间选点的问题
只看楼主 加入收藏
天天涯涯
Rank: 4
等 级:业余侠客
帖 子:215
专家分:267
注 册:2011-10-17
结帖率:94.74%
收藏
已结贴  问题点数:20 回复次数:5 
问一个关于区间选点的问题
建一个坐标系,x轴的上方是海洋,下方是陆地。海洋上散乱分布着一些岛屿,在岸上建立雷达站使得所有的岛都在监视范围内。
第一行输入小岛的数目n和雷达的监视半径d。(当n=d=0时输入结束)
之后n行输入各个小岛的坐标。
求所需雷达的最小数目。
样例输入
3 2
1 2
-3 1
2 1

1 2
0 2

0 0
样例输出
Case 1: 2
Case 2: 1


#include <stdio.h>
#include <math.h>
int main()
{
    int n,d,co=1;
    while(scanf("%d%d",&n,&d),n&&d)
    {
        int i,j,flag=0,k;
        float x[1002],y[1002];
        for(i=0;i<n;i++)   
        {
            scanf("%f%f",&x[i],&y[i]);
            if(y[i]>d)
            {
                flag=1;
                continue;
            }
            x[i]=x[i]-sqrt(d*d-y[i]*y[i]);   //以每一个岛为圆心,d为半径,所画的圆与x轴的交点
            y[i]=x[i]+sqrt(d*d-y[i]*y[i]);
        }
        if(flag)
        {
            printf("Case %d: -1\n",co);
            break;
        }
        float x1,y1;
        for(i=1;i<n;i++)  //插入排序
        {
            x1=x[i];
            y1=y[i];
            for(j=0;j<i;j++)
                if(y[i]<y[j])
                    break;
            for(k=i-1;k>=j;k--)
            {
                x[k+1]=x[k];
                y[k+1]=y[k];
            }
            x[j]=x1;
            y[j]=y1;
        }
        float begin=x[n-1],last=y[n-1];
        int num=1;
        for(k=n-2;k>=0;k--)  //在区间内找点,使得点最少,并且保证每个区间内最少有一个点
        {
            if(x[k]>=begin)
            {
                begin=x[k];
                last=y[k];
                continue;
            }
            if(begin>x[k]&&begin<=y[k])   
            {
                last=y[k];
                continue;
            }
            if(begin>y[k])
            {
                begin=x[k];
                last=y[k];
                num++;
            }
        }
        printf("Case %d: %d\n",co,num);
        co++;
    }
    return 0;
}

大哥帮忙看看为什么提交不上。。。
搜索更多相关主题的帖子: 海洋 雷达站 include 坐标系 
2012-03-24 20:43
天天涯涯
Rank: 4
等 级:业余侠客
帖 子:215
专家分:267
注 册:2011-10-17
收藏
得分:0 
求解释
2012-03-24 20:59
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:14 
请发上来原题网址。

         if(flag)
         {
             printf("Case %d: -1\n",co);
             break;
         }
这段就不对,不应该用break,该用continue。

重剑无锋,大巧不工
2012-03-24 21:27
天天涯涯
Rank: 4
等 级:业余侠客
帖 子:215
专家分:267
注 册:2011-10-17
收藏
得分:0 
http://acm.
2012-03-24 21:47
天天涯涯
Rank: 4
等 级:业余侠客
帖 子:215
专家分:267
注 册:2011-10-17
收藏
得分:0 
改了也不对
2012-03-24 21:48
天天涯涯
Rank: 4
等 级:业余侠客
帖 子:215
专家分:267
注 册:2011-10-17
收藏
得分:0 
beyondyf交不上
2012-03-24 21:48
快速回复:问一个关于区间选点的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.101392 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved