Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

求大神指出不对的地方,WA的神经错乱了……

Posted by godofwa2 at 2012-07-20 15:38:48 on Problem 1584 and last updated at 2012-07-20 15:39:51
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator