注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 3347 Kadj Squares 扩大数据化整数  

2011-05-04 15:23:09|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://poj.org/problem?id=3347

边长不等的正方形,互不相交的摆放在x轴上,且边长与x轴y轴成45度角。(具体可以看题目图例)

要注意正方形的顶点不能越过y轴。

很麻烦的一道几何道,必须要对边长扩大sqrt(2)倍化整数,来避免精度问题。

求每个正方形在x轴上的区间:若正方形i与正方形i-1相邻,则可直接计算出正方形i的顶点位置x。不相邻的话就要依次让正方形i与0~i-1的正方形相邻求出相应的顶点位置x,取最大值。

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct it
{
 int a,b,len;
 int num;
}q[55];
bool cmp(it a,it b)
{
 return a.a<b.a;
}
int main()
{
 int n,i,j,k,x[55],ans[55],max,flag;
 while(scanf("%d",&n),n)
 {
  for(i=0;i<n;i++)
     {
   scanf("%d",&q[i].len);
   if(i==0)
    x[i]=q[i].len;
   else if(q[i].len<=q[i-1].len)
    x[i]=x[i-1]+2*q[i].len;
   else if(q[i].len<=2*q[i-1].len)
    x[i]=x[i-1]+2*q[i-1].len;
   else
   {
    x[i]=-1;
    for(j=0;j<i;j++)
    {
     if(q[i].len<=q[j].len)
         max=x[j]+2*q[i].len;
     else
      max=x[j]+2*q[j].len;
     if(x[i]<max)
      x[i]=max;
    }
   }
   q[i].a=x[i]-q[i].len;
   q[i].b=x[i]+q[i].len;
   if(q[i].a<0)
   {
    q[i].a=0;
    q[i].b=2*q[i].len;
    x[i]=q[i].len;
   }
   q[i].num=i+1;
     }
     sort(q,q+n,cmp);
     k=0;
     for(i=0;i<n;i++)
     {
    max=q[i].a;flag=0;
       for(j=0;j<i;j++)
       {
    if(q[j].b>=q[i].b)
    {
     flag=1;
     break;
    }
    if(q[j].len>q[i].len&&q[j].b>=max)
    max=q[j].b;
   }
    if(!flag)
    for(j=i+1;j<n;j++)
    {
     if(q[j].a<=max&&q[j].len>q[i].len)
     {
      flag=1;
      break;
     }
   }
   if(!flag)
    ans[k++]=q[i].num;
  }
  sort(ans,ans+k);
  printf("%d",ans[0]);
  for(i=1;i<k;i++)
  printf(" %d",ans[i]);
  printf("\n");
 }
 return 0;
}

  评论这张
 
阅读(219)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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