#include #define MAX 1024 #define INF 0xffffff int n, xb, yb, v, o[2*MAX],value[4*MAX]; /*value - hodnoty int. stromu*/ int p[4*MAX], /*p - vrchol int. stromu je pokryt*/ int cmp(const void *a, const void *b) /*porovnání dle $y$*/ { return ((int *)a)[2] - ((int *)b)[2]; } int cmp2(const void *a, const void *b) /*a dle $x$*/ { return *(int *)a - *(int *)b; } int find (int node, int lnode, int rnode, int x) /*najdi nejbližší nižší plošinku*/ { int m = (lnode + rnode) / 2; if (p[node]) /*máme koncový vrchol*/ return value[node]; if (x <= o[m]) /*jinak jdeme vlevo nebo vpravo*/ return find(2 * node, lnode, m, x); return find(2 * node + 1, m+1, rnode, x); } void add(int node, int lnode, int rnode, int from, int to, int index) /*přidej plošinku do int. stromu*/ { int m; if (o[lnode] >= from && o[rnode] <= to){ p[node] = 1; value[node] = index; } else { if (p[node] && lnode < rnode){ /*rozdělíme interval na dva menší*/ p[2 * node] = p[2 * node + 1] = 1, p[node] = 0; value[2 * node] = value[2 * node + 1] = value[node]; } m = (lnode + rnode) / 2; /*a pokryjeme zbytek*/ if (from <= o[m]) add(2 * node, lnode, m, from, to, index); if (o[m] < to) add(2 * node, m + 1, rnode, from, to, index); } } int main(void) { int i, on, j, k, d[MAX][3], lpred[MAX], rpred[MAX], lsum[MAX], rsum[MAX]; int left, right, maxi, max, result[MAX]; bzero(o, MAX*sizeof(int)); scanf("%d", &n); /*načítáme*/ scanf("%d %d %d", &xb, &yb, &v); for (i=0; i v) lpred[i] = n; rpred[i] = find(1, 0, n, d[i][1]); if (d[i][2] - d[rpred[i]][2] > v) lpred[i] = n; add(1, 0, on, d[i][0], d[i][1], i); } lsum[n] = rsum[n] = INF; lsum[0] = rsum[0] = 0; for (i=1; i rsum[right] + abs(d[i][0] - d[right][1])) rsum[i] = lsum[right] + abs(d[i][0] - d[right][0]); else if (right) rsum[i] = rsum[right] + abs(d[i][0] - d[right][1]); else rsum[i] = 0; } for (max=0, maxi=0, i=0; i max && yb >= d[i][2] && d[i][0] < xb && d[i][1] > xb){ max = d[i][2]; maxi = i; } } i = maxi, j = 0;/*a vysledujeme zpáteční cestu*/ while (!lpred[i] && !rpred[i] && i != n){ if (xb - lsum[maxi] < rsum[maxi] - xb){ i = lpred[maxi]; result[j] = 'l'; } else { i = rpred[maxi]; result[j] = 'r'; } j++; } if (i == n) printf("Chudak blecha asi se nam urazi!\n"); else { for (i=0; i