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

zxj015

 
 
 

日志

 
 

poj 1584 A Round Peg in a Ground Hole 点到直线的距离 点是否在多边形内 多边形是否为凸  

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

  下载LOFTER 我的照片书  |

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

给一个多边形,和一个圆形的钉子,判断多边形是否为凸多边形,若为凸多边形判断钉子能否被包含在多边形内。

判断是否为凸多边形:相邻的两条边做叉乘i*(i+1)都大于零(假定顶点为逆时针排序,顺时针反之)则为凸多边形。

判断圆心是否在多边形内:设o为圆心,s1,s2为相邻顶点,若叉乘(s1s2)*(s1o)都大于零则圆心在多边形内部。(假定顶点为逆时针排序,顺时针反之)

之后找圆心到多边形边的最短距离,若最短距离小于圆半径必定不会包含在多边形内。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#define eps 1e-8
using namespace std;
struct point
{
 double x,y;
}p[10000];
double multi(point p0,point p1,point p2)
{
 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
point inter(point u1,point u2,point v1,point v2)
{
  point ret=u1;
  double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
          /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
  ret.x+=(u2.x-u1.x)*t;
  ret.y+=(u2.y-u1.y)*t;
  return ret;
}

bool is(point s1,point e1,point s2,point e2)
{
 return  (max(s1.x,e1.x)>=min(s2.x,e2.x))&&
      (max(s2.x,e2.x)>=min(s1.x,e1.x))&&
     (max(s1.y,e1.y)>=min(s2.y,e2.y))&&
     (max(s2.y,e2.y)>=min(s1.y,e1.y))&&
     (multi(s1,s2,e1)*multi(s1,e1,e2)>=0)&&
      (multi(s2,s1,e2)*multi(s2,e2,e1)>=0);
}
point pt(point p,point t1,point t2)
{
 point t=p;
 t.x+=t1.y-t2.y;
 t.y+=t2.x-t1.x;
 return inter(p,t,t1,t2);
}
double dis(point a,point b)
{
 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void work(point t,int n,double r)
{
 int i;
 double flag;
 point a;
 flag=multi(p[0],p[1],p[2]);//做顶点顺、逆时针标记
 for(i=1;i<n-1;i++)
 if(flag*multi(p[i],p[i+1],p[i+2])<-eps)
 {
  printf("HOLE IS ILL-FORMED\n");
  return;
 } 
 for(i=0;i<n;i++)
 {
  a=pt(t,p[i],p[i+1]);
  if(multi(p[i],p[i+1],t)*flag<-eps)//圆心不在多边形内部
  {
   printf("PEG WILL NOT FIT\n");
   return;
  }
  if(dis(a,t)-r<-eps)
  {
   printf("PEG WILL NOT FIT\n");
   return;
  }
 }
 printf("PEG WILL FIT\n");
}
int main()
{
 int i,n;
 double r;
 point t;
 while(scanf("%d",&n),n>=3)
 {
  scanf("%lf%lf%lf",&r,&t.x,&t.y);
  for(i=0;i<n;i++)
   scanf("%lf%lf",&p[i].x,&p[i].y);
  p[n]=p[0];
  work(t,n,r);
 }
 return 0;
}
   
   
  
    
    
   
  
   
   
   
  
  

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

历史上的今天

评论

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

页脚

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