| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
求大牛赐教为啥我这个代码跑出来时间是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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator