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

zxj015

 
 
 

日志

 
 

poj 3335 Rotating Scoreboard 半平面交  

2011-05-06 21:31:39|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://poj.org/problem?id=3335
给定一个多边形,判断是否存在核,点顺时针给出。
半平面交模板直接用。

#include<cmath>
#include<algorithm>
using namespace std;

const double MAX =100000000;
const double pi =acos(-1.0);
const double eps=1e-8;
int m,s;
struct node
{
double x,y; //注意类型
}tr[110],p[110],q[110];
int sig(double k)
{
return (k<-eps)?-1:(k>eps);
}
void interect(node x,node y,double a,double b,double c)
{
double u=fabs(a*x.x+b*x.y+c);
double v=fabs(a*y.x+b*y.y+c);
q[++s].x=(x.x*v+y.x*u)/(u+v);
q[s].y=(x.y*v+y.y*u)/(u+v);
}
//利用半平面切割
void cut(double a,double b,double c)
{
s=0;
int i;
for(i=1;i<=m;i++) //遍历所有顶点是否能观察到该边
{
   if(sig(a*p[i].x+b*p[i].y+c)>=0)//因为线段是顺时针给出的,如果是逆时针就是<=0
   {
    q[++s]=p[i]; //若是则存储
   }
   else
   {
    if(sig(a*p[i-1].x+b*p[i-1].y+c)>0)//逆时针就是<0
     interect(p[i-1],p[i],a,b,c);
    if(sig(a*p[i+1].x+b*p[i+1].y+c)>0)//逆时针就是<0
     interect(p[i+1],p[i],a,b,c);
   }
}
//最后的p数组存放半平面的点集合
for(i=1;i<=s;i++) 
   p[i]=q[i];
p[s+1]=p[1],p[0]=p[s];
m=s;
}

int main()
{
int n,i,j,t;
scanf("%d",&t);
while(t--)
{
   scanf("%d",&n);
   for(i=0;i<n;i++)
   {
    scanf("%lf%lf",&tr[i].x,&tr[i].y);
    p[i+1]=tr[i]; //初始化边界
   }
   tr[n]=tr[0];
   p[n+1]=p[1];p[0]=p[n];
   m=n;
   double a,b,c;
   for(i=0;i<n;i++)
   {
    a=tr[i+1].y-tr[i].y; //计算出相邻两点所在直线ax+by+c=0
    b=tr[i].x-tr[i+1].x;
    c=tr[i+1].x*tr[i].y-tr[i].x*tr[i+1].y;
    cut(a,b,c);
   }
   if(!m) puts("NO");//这里如果有一个点,或者一条线段都可以,所以判断m是不是等于0就行了,不用判断面积
   else puts("YES");
}
return 0;
}


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

历史上的今天

评论

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

页脚

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