| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
求大神指出不对的地方,WA的神经错乱了……#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct point
{
double x,y;
}pnt[200],res[200],a;//装原来的点,转为凸包后的点,还有圆心坐标
int n;
double r,ax,ay,mul[200];//mul临时存储叉积
double multi(point &a,point &b,point &o)//计算叉积
{
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
bool operator <(const point &l,const point &r)//对点排序用
{
return l.y<r.y || (l.y==r.y && l.x<r.x);
}
int graham()//graham扫描,得到凸包存放在res中,返回凸包的定点数top
{
int i,len,k=0,top=1;
sort(pnt,pnt+n);
if (n==0) return 0;res[0]=pnt[0];
if (n==1) return 1;res[1]=pnt[1];
if (n==2) return 2;res[2]=pnt[2];
for (i=2;i<n;i++)
{
while(top && multi(pnt[i],res[top],res[top-1])>0)
top--;
res[++top]=pnt[i];
}
len=top;
res[++top]=pnt[n-2];
for (i=n-3;i>=0;i--)
{
while(top!=len && multi(pnt[i],res[top],res[top-1])>0)
top--;
res[++top]=pnt[i];
}
return top;
}
bool pinplg()//判断点是否在凸包里面
{
int i;
for (i=0;i<n;i++)
{
mul[i]=multi(res[i],res[(i+1)%n],a);
if (mul[i]<0)//注意凸包里面的点是逆时针排序的
return false;
}
return true;
}
double dis(const point &a,const point &b)//两点距离
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool smallr()//判断圆心到每条边的距离是否小于给出半径
{
int i;
for (i=0;i<n;i++)
{
if ((fabs(mul[i])/dis(res[i],res[(i+1)%n]))<r)//用叉积除以底边长得到高……
return false;
}
return true;
}
int main()
{
int i,j;
while(~scanf("%d%lf%lf%lf",&n,&r,&ax,&ay))
{
a.x=ax;
a.y=ay;
for (i=0;i<n;i++)
{
scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
for (j=0;j<i;j++)
if (pnt[i].x==pnt[j].x && pnt[i].y==pnt[j].y)
break;
if (j<i)//去除重点
{
i--;n--;
}
}
if (graham()<n)//给出的点构成不了凸包
{
printf("HOLE IS ILL-FORMED\n");
}
else
{
if (pinplg())//圆心在凸包里面
{
if (smallr())//圆心到各边的记录小于半径
{
printf("PEG WILL FIT\n");
}
else
{
printf("PEG WILL NOT FIT\n");
}
}
else
{
printf("PEG WILL NOT FIT\n");
}
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator