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

求高手差错,提交总是WR

Posted by zkk at 2011-10-03 22:15:16


#include<iostream>
#include<cmath>
using namespace std;

struct Point
{
	int x;
	int y;
};

struct Point list[1000];

int stack[1000],top;

int CrossProd(Point A,Point B,Point C)                           //叉乘AB*AC
{

	return(B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}

double Length(Point A,Point B)
{
	return(sqrt((double)((A.y-B.y)*(A.y-B.y)+(A.x-B.x)*(A.x-B.x))));
}

void graham(int N)
{
	int i;
	for(i=0;i<3;i++)
		stack[i]=i;
	top=2;
	for(i=3;i<N;i++)
	{
		while(CrossProd(list[stack[top-1]],list[stack[top]],list[i])>=0)
		{
		
			top--;
			if(top==0)
				break;
		
		}
		top++;
		stack[top]=i;

	}


}




int main()
{
	int N,L,i,t=0;
	Point *pt;
	double len=0;
	while(cin>>N>>L)
	{
		len=0;
		pt=new Point[N];
		for(i=0;i<N;i++)
			cin>>pt[i].x>>pt[i].y;                        
        

		for(i=1,t=0;i<N;i++)
		{
			if(pt[i].y<pt[t].y)
				t=i;
			if((pt[i].y==pt[t].y)&&(pt[i].x<pt[t].x))
				t=i;
		}



		
		for(int j=0;j<N;j++)
		{
			if(t+j<N)
			{
    			list[j].x=pt[t+j].x;
		        list[j].y=pt[t+j].y;  
			}                                    
			else
			{
				list[j].x=pt[t+j-N].x;
		        list[j].y=pt[t+j-N].y; 
			}
			                                      

		}
		
		
        free(pt);
		graham(N);
        
		for(i=0;i<top;i++)
			len+=Length(list[stack[i]],list[stack[i+1]]);
		
        cout<<len<<endl;
		len+=(2*3.141592653*L+Length(list[stack[top]],list[stack[0]]));
//		printf("%.f\n",len);
		cout<<(int)(len+0.5)<<endl;
	
	}
	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