#include #include #include #define EPSILON 1.0e-15 #define MAXN 1024 struct point { long double x, y; struct point *next[2]; long double last_time[2]; }; #define NO_LAST_TIME -1.0L struct point points[MAXN]; int num_points; long double dist (const struct point *a, const struct point *b) { return hypotl (a->x - b->x, a->y - b->y); } long double product (const struct point *s1, const struct point *e1, const struct point *s2, const struct point *e2) { return (e1->x - s1->x) * (e2->y - s2->y) - (e1->y - s1->y) * (e2->x - s1->x); } struct point * find_next (const struct point *prev, const struct point *last, long double length) { struct point *p, *best; best = NULL; for (p = points + 1; p < points + num_points; p++) { if (p == last || dist (p, last) > length + EPSILON) continue; if (product (prev, last, prev, p) <= 0.0L) { if (best != NULL) { long double diff; diff = product (last, best, last, p); if (fabsl (diff) > EPSILON && diff < 0.0L) continue; if (fabsl (diff) <= EPSILON) { /* last, best a p jsou na jedne primce, tedy je na teto primce i prev. Pokud mozno chceme vybrat bod ve smeru prev->last, vybereme tedy bod vzdalenejsi od prev. */ if (dist (prev, best) > dist (prev, p)) continue; } } best = p; } } return best; } int main (void) { struct point *p, *top; const struct point *prev; long double length; scanf ("%u", &num_points); num_points++; top = NULL; for (p = points + 1; p < points + num_points; p++) { scanf ("%Lf%Lf", &p->x, &p->y); p->next[0] = NULL; p->next[1] = NULL; p->last_time[0] = NO_LAST_TIME; p->last_time[1] = NO_LAST_TIME; if (top == NULL || top->y < p->y || (top->y == p->y && top->x < p->y)) top = p; } scanf ("%Lf", &length); p = top; points[0].x = p->x - 1; points[0].y = p->y; prev = points; for (;;) { struct point **next; int type; long double *last; if (p->y > prev->y || (p->y == prev->y && p->x > prev->x)) type = 0; else type = 1; next = p->next + type; if (*next == NULL || dist (*next, p) > length + EPSILON) { *next = find_next (prev, p, length); if (*next == NULL) break; } length -= dist (*next, p); prev = p; p = *next; last = p->last_time + type; if (*last != NO_LAST_TIME) { long double cycle; cycle = *last - length; if (length >= cycle) length -= floorl (length / cycle) * cycle; } *last = length; } printf ("Provazek se namota na kolik na souradnicich %Lf, %Lf\n", p->x, p->y); return EXIT_SUCCESS; }