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 jokes000 at 2011-06-01 22:00:56 on Problem 1113
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
#define pi 3.14159265
int N,L;

struct point
{
	int x,y;	
};

struct point pnt[1005],res[1005];

bool mult(point sp, point ep, point op)
{
	return (sp.x - op.x) * (ep.y - op.y) >= (ep.x - op.x) * (sp.y - op.y);
};

bool operator < (const point &l, const point &r)
{
	return l.y < r.y || (l.y == r.y && l.x < r.x);
};

int graham(int n)
{
	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 && mult(pnt[i], res[top], res[top-1]))
			top--;
		res[++top] = pnt[i];
	}
	
	len = top; res[++top] = pnt[n - 2];
	for (i = n - 3; i >= 0; i--) 
	{
		while (top!=len && mult(pnt[i], res[top],
			res[top-1])) top--;
		res[++top] = pnt[i];
	}
	return top; // 返回凸包中点的个数
}

double Distance( point a, point b )
{
	return sqrt( (double)(a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );	
}

int main()
{
	int i,x,y,nr;
	double dis;
	
	while ( scanf( "%d%d",&N,&L ) != EOF )
	{
		for ( i = 0; i < N; ++ i )
		{
			scanf( "%d%d",&pnt[i].x,&pnt[i].y );	
		}	
		
		nr = graham(N);
		//printf("%d\n",nr);
		dis = 0;
		
		for ( i = 1; i < nr; ++ i )
		{
			dis += Distance(res[i-1], res[i]);	
		}
		dis += Distance(res[0],res[nr-1]);
		dis += 2 * pi * L;
		
		printf("%d\n",(int)(dis+0.5));
		
	}
}

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