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