//poj1584
//题意:给出一系列的点,给出一个圆,判断这些点按一定方向能否构成凸多边形,
//若是凸多边形,看这个圆是否在多边形内。
//解题思路:
//1. 凸多边形的判断:
//分别用0,1,2来表示叉积的值为零,正,负。对每相邻的三个点进行叉乘,
//而相邻的两个叉乘的值不能异号(根据叉乘可判断出第二个向量在第一个向量的顺时针或逆时针方向),
// 当遍历完所有相邻的三点时没有出来异号那就是凸多边形了。
//附:若有要求相邻边不共线的话就多一个叉值不为0的判断就可以了。
//2.判断圆心是否在凸多边形内,根据上面相同的道理,判断圆心是否在边的同一侧。
//3.判断点到直线的距离(本是点到线段的,但已经确定是凸多边形就不需要了),利用公式即可。
//代码如下:
#include<iostream>
#include<cstdio>
#include<math.h>
#define eps 1e-8
#define _sign(x) (x>eps ? 1: x<-eps ? 2:0)
struct Point{double x,y;};
struct Line{double a,b,c;};
struct Circle{double r;Point center;};
double xmult(Point p1,Point p2,Point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//凸多边形的判断
int isConvex(int n,Point *p)
{
int i,s[3]={1,1,1};
for(i=0;i<n && s[1]|s[2];i++)
s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
return s[1]|s[2];
}
//判断点在凸多边形内
int insideConvex(Point q,int n,Point *p)
{
int i,s[3]={1,1,1};
for(i=0;i<n && s[1]|s[2];i++)
s[_sign(xmult(p[(i+1)%n],q,p[i]))]=0;
return s[1]|s[2];
}
//点到直线距离
double poToLine(Point p,Line l)
{
return fabs(l.a*p.x+l.b*p.y+l.c)/sqrt(l.a*l.a+l.b*l.b);
}
//两点成线
Line twoPoLine(Point p1,Point p2)
{
Line l;
l.a=p1.y-p2.y;
l.b=p2.x-p1.x;
l.c=p1.x*p2.y-p2.x*p1.y;
return l;
}
Point p[10000];
int main()
{
int n;
Circle c;
while(scanf("%d",&n),n>2)
{
int i;
scanf("%lf%lf%lf",&c.r,&c.center.x,&c.center.y);
for(i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
if(isConvex(n,p))
{
if(insideConvex(c.center,n,p))
{
for(i=0;i<n;i++)
{
Line l=twoPoLine(p[i],p[(i+1)%n]);
if(poToLine(c.center,l)-c.r<0.0)
{printf("PEG WILL NOT FIT\n");break;}
}
if(i==n)printf("PEG WILL FIT\n");
}
else
printf("PEG WILL NOT FIT\n");
}
else
printf("HOLE IS ILL-FORMED\n");
}
return 0;
}
分享到:
相关推荐
POJ1584 -A Round Peg in a Ground Hole 测试数据。数据来源 Mid-Atlantic 2003 问题D
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
北大POJ3252-Round Numbers 解题报告+AC代码
北大POJ1936-All in All 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2388-Who's in the Middle 解题报告+AC代码
北大POJ1942-Paths on a Grid 解题报告+AC代码
POJ2942-Knights of the Round Table 【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2488-A Knight's Journey 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
对于POJ1852题目和详细的解答,代码已经通过
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告