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

求大牛赐教

Posted by xiazhiray at 2011-05-15 23:08:17 on Problem 1328
为啥我这个代码跑出来时间是16MS,如何改进能做到0MS呢?

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

class point
{
public:
	float x;
	float y;
};

int compare(const void *arg1, const void *arg2)
{
	const point * a = (const point *)arg1;
	const point * b = (const point *)arg2;

	if (a->x < b->x)
	{
		return -1;
	}

	return 1;
}

int main ()
{
	int c = 0;
	do 
	{
		c ++;
		int n;
		int d;
		scanf ("%d %d", &n, &d);
		if (n == 0 && d == 0)
		{
			break;
		}

		point p[1000];
		for (int i = 0; i < n; i ++)
		{
			scanf ("%f %f", &((p+i)->x), &((p+i)->y));
		}

		int r = 0;
		int s = 0;
		for (int j = 0; j< n; j ++)
		{
			float xdst = (p+j)->y;
			if (xdst > d)
			{
				r = -1;
				goto report;
			}

			float xspan = (float)(sqrt (d*d - xdst*xdst));
			(p+j)->y = (p+j)->x - xspan;
			(p+j)->x = (p+j)->x + xspan;
		}

		qsort (p, n, sizeof(point), compare);
		
		do
		{
			r ++;
			int pre = s;
			s ++;
			while (s < n && (p+pre)->x >= (p+s)->y)
			{
				s ++;
			}
		}while (s < n);

report:
		printf ("Case %d: %d\n", c, r);
	}while (true);
	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