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