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

1228怎么WA了?有什么特殊情况吗?或者是我题目理解错了吗?谢谢~

Posted by ic07343 at 2008-01-30 21:39:21
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
const int maxN=1000;
const double pi=3.141592;
const double eps=0.0000001;
double a1,a2,dis1,dis2;
struct node
{
	double x,y;
}nail[maxN+10],p;
int area(node a,node b,node c)
{
	return (a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y));
}
int cmp(void const *e1,void const *e2)
{
	
	node *p1,*p2;
	p1=(node *)e1;
	p2=(node *)e2;
    a1=atan2(p1->y-p.y,p1->x-p.x);
	a2=atan2(p2->y-p.y,p2->x-p.x);
	if(a1<eps)
		a1+=2*pi;
    if(a2<eps)
		a2+=2*pi;
	if(a1<a2)
		return -1;
	else
		return 1;
	
}
		
    
int main()
{
	int cas,j,i,n,count;
	scanf("%d",&cas);
	for(i=1;i<=cas;i++)
	{
		scanf("%d",&n);
		
		count=0;
		p.x=0;
		p.y=0;
		for(j=0;j<=n-1;j++)
		{	
			scanf("%lf%lf",&(nail[j].x),&(nail[j].y));
			p.x+=nail[j].x;
			p.y+=nail[j].y;
		}
		if(n==1||n==2)
		{
			printf("NO\n");
			continue;
		}
		(p.x)/=n;
		(p.y)/=n;
		qsort(nail,n,sizeof(node),cmp);
	    
        bool flag=0,line=0;
        for(j=0;j<=n-1;j++)
		{	
			if(area(nail[j],nail[(j+1)%n],nail[(j+2)%n])==0&&count==0)	
				count++;
			else if(area(nail[j],nail[(j+1)%n],nail[(j+2)%n]))	
			{	count--;
			    line=1;
			}
         
		
			if(count<0)
			{	
				flag=1;
				break;
			}
		}
		if(flag||line==0)
			printf("NO\n");
		else
			printf("YES\n");
	


//		for(j=0;j<=n-1;j++)
//			printf("%lf%lf\n",nail[j].x,nail[j].y);
	}
	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