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

zxj015

 
 
 

日志

 
 

poj 1264 hdu 1616 SCUD Busters 凸包+面积计算  

2011-03-28 16:59:21|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题很看郁闷,看了很久才明白是什么意思。大致就是有数个国家,每个国家有数个房子,房子相互连接组成的最小周长的多边形为该国家领土,当输入-1时国家输入完毕,接下来是多个炸弹的降落地点。国家的个数最多为20,炸弹可以无限个。若炸弹在某个国家的领土内爆炸(包括边),则可看成该国领土所有面积被炸(当然原文不是这样说),求所有被炸的面积。
思路其实很明了,求出每个国家的凸包,若炸弹在凸包内,则计算所有这样凸包面积的和。要注意可能多个炸弹在落在同一个国家内,这时候只要算一个即可。
判断点在多边形内的算法有很多种,这里用到的是外积法:设待判断的点为p,逆时针或顺时针遍例多边形的每个点vn,将两个向量<p, vn>和<vn, vn + 1>做外积。如果对于多边形上所有的点,外积的符号都相同(顺时针为负,逆时针为正),则可断定p在多边形内。外积出现0,则表示p在边上,否则在多边形外。
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int num,top,ii;
struct node
{
   int x;
   int y;
}a[105],mis[50005]; //b当栈使用
struct
{
      node b[25];
      int to;
}an[25];
int cmp(const void *c,const void *d)
{
   int ans;
   struct node *p1=(node *)c;
   struct node *p2=(node *)d;
   ans=(p1->x-a[0].x)*(p2->y-a[0].y)-(p2->x-a[0].x)*(p1->y-a[0].y);        
   if (ans>0) return -1;
   else if (ans<0) return 1;
   else 
   {
     if (abs(a[0].x-p1->x)<abs(a[0].x-p2->x)) return 1;
      return -1;
   }
}
int find( int p2,int p1,int p0)   //叉乘判断转向p0p1*p0p2
{
    return (an[ii].b[p1].x-an[ii].b[p0].x)*(a[p2].y-an[ii].b[p0].y)-(a[p2].x-an[ii].b[p0].x)*(an[ii].b[p1].y-an[ii].b[p0].y);
}
int find2( node p2,node p1,node p0)   //叉乘判断转向p0p1*p0p2
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
void Graham(int n)
{
     int i;
     a[n]=a[num];       //将y最小的点当成极坐标的原点
     a[num]=a[0];
     a[0]=a[n];
     qsort(a+1,n-1,sizeof(a[0]),cmp);  //按极角由小到大(逆时针)排序,有多个极角相同的,按离原点近的排
     an[ii].b[0]=a[0];
     an[ii].b[1]=a[1];
     top=1;
     for (i=2;i<n;i++)
     {
         while (find(i,top,top-1)<0) top--;     //如果向右转,就把栈顶退一个,直到新加入的点是向左转为止
              an[ii].b[++top]=a[i];                   //进栈
     }
}
int main ()
{
         // freopen ("1.txt","r",stdin);
    int n,i,j,k,h,minx=10005,miny=10005,dis,max,misnum,sum;
    double area;
    ii=0;
    while(scanf("%d",&n),n!=-1)
    {
    minx=10005;miny=10005;
    for (i=0;i<n;i++)
    {
        scanf("%d %d",&a[i].x,&a[i].y);
        if (a[i].y<miny || (miny==a[i].y && a[i].x<minx))       //记录y值最小的点 有多个时 选x最小的
        {
            miny=a[i].y;minx=a[i].x;num=i;
        }
    }
     Graham(n);
     an[ii].to=top;
     ii++;
     }
      i=0;
     while(scanf("%d%d",&mis[i].x,&mis[i].y)!=EOF)
          i++;
     misnum=i;area=0;
     for(i=0;i<ii;i++)
     {
          for(j=0;j<misnum;j++)
          {
               for(k=0;k<=an[i].to;k++)
               {
                    if(k==an[i].to)
                    {
                         if(find2(mis[j],an[i].b[0],an[i].b[k])<0)
                               break;
                    }                
                    else if(find2(mis[j],an[i].b[k+1],an[i].b[k])<0)
                         break;
               }
                if(k==an[i].to+1)  //mis[j]若点在凸包内计算凸包面积 
                {
                     sum=0;
                     for(h=0;h<an[i].to;h++)
                          sum+=an[i].b[h].x*an[i].b[h+1].y-an[i].b[h].y*an[i].b[h+1].x;
                      sum+=an[i].b[h].x*an[i].b[0].y-an[i].b[h].y*an[i].b[0].x;
                      area+=sum*1.0/2;
                      break;//跳出因为有能可能多点在同一个凸包内 
                }
          }
     }
     printf("%.2f\n",area);
   //  system("pause");
     return 0;
}
       

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

历史上的今天

评论

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

页脚

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