PKU 1328 贪心

算法:
1 排序 算出每个岛可安雷达的最左边坐标和最右边坐标 左座标按升序排列 左相同时右按照降序排列
2 贪心选取 更新最右边的坐标 如果下一个的左座标大于当前最右边 数目加一 否则的话更新最右边的值

排序的时候因为是DOUBLE 所以那个qsort还要小小的注意下写法

代码如下
/**********************
Author: WHU_Victordu
Created Time: 2007-12-26
File Name: pku1328.cpp
  Description: 
   **************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct Point
{
        double left;
        double right;
}points;

int cmp(const void *p1, const void *p2)
{
   Point I1 = *(Point *)p1;
   Point I2 = *(Point *)p2;
   double temp = I1.left - I2.left;
   if (temp > 0.0) return 1;
   else if (temp < 0.0) return -1;
   else {
      temp = I2.right - I1.right;
      if (temp > 0.0) return 1;
      else return -1;
   }
}


int main()
{
    Point points[1005];

    int n,d,x[1005],y[1005],i,dd,cnt,flag;
    int t=0;
    double sqrtdy,right;
   
    while(scanf("%d%d",&n,&d)&&!(n==0&&d==0))
    {
      t++;
      flag=0;
      for(i=0;i<n;i++)
      {
       scanf("%d%d",&x[i],&y[i]);
       if(y[i]>d) flag=1;
       }
      if(flag)
      { 
         printf("Case %d: %d\n",t, -1);
         continue;
      }
     
      dd=d*d;
      for (i = 0; i < n; i++)
       {
         sqrtdy = sqrt(dd - y[i]*y[i]);
         points[i].left = x[i]-sqrtdy;
         points[i].right =x[i]+ sqrtdy;
      }

     
      qsort(points,n,sizeof(Point),cmp);
     
      for(i=0;i<n;i++)
      {
        printf("%d %d\n",points[i].left,points[i].right);
      }
     
      cnt=1;
      right=points[0].right;
      for(i=1;i<n;i++)
      {
        if(points[i].left>right)
        {
         cnt++;
         right=points[i].right;
        }
        else {
            if (points[i].right < right)
               right = points[i].right;
         }
      }
     
    printf("Case %d: %d\n",t,cnt);
     
    }
   
}

posted on 2007-12-26 14:52 Victordu 阅读(1534) 评论(8)  编辑 收藏 引用

评论

# re: PKU 1328 贪心 2007-12-26 17:02 winsty

都用cpp做扩展名了
为什么不用STL里的Sort啊...  回复  更多评论   

# re: PKU 1328 贪心 2007-12-26 17:59 koson

supporting. I have solved this problem. But i think use the sort is more convenience. -_-  回复  更多评论   

# re: PKU 1328 贪心 2007-12-26 22:19 万连文

这就是传说中的acm,应该不允许使用吧,提倡创造轮子。  回复  更多评论   

# re: PKU 1328 贪心 2007-12-26 22:26 Victordu

谢谢 我很多地方是还不规范@winsty
  回复  更多评论   

# re: PKU 1328 贪心 2007-12-26 22:27 Victordu

同谢指教@koson
  回复  更多评论   

# re: PKU 1328 贪心 2007-12-26 22:27 Victordu

STL是可以用的 当然是在效率满足的情况下@万连文
  回复  更多评论   

# re: PKU 1328 贪心 2008-09-01 22:46 allen303allen

为啥要考虑可按雷达的最左和最右?只贪心一个方向就可以了吧。  回复  更多评论   

# re: PKU 1328 贪心 2009-01-19 20:45 shk3

似乎有问题  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿(5)

随笔档案(46)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜