#include #include #include #include #include #define N_MAX 100000 int n; struct bod { float s[2]; /* souřadnice bodu v rovině */ int b[2]; /* souřadnice bloku, do nějž patří */ int blok; } body[N_MAX]; struct { int s[2]; /* souřadnice */ int bodu; /* počet bodů v bloku */ unsigned char hrany[5][5]; /* se kterými z možných 24 bloků sousedí */ bool navstiveno; /* zda byl již navštíven při procházení */ bool pruseciku; /* počet průsečíků s "paprskem" na cestě * od počátečního vrcholu (bloku) sem */ } bloky[N_MAX]; /* dvě porovnávací funkce pro qsort */ int porovnat_bloky(const void *va, const void *vb) { const struct bod *a = va, *b = vb; return a->b[1] == b->b[1] ? a->b[0] - b->b[0] : a->b[1] - b->b[1]; } int por_sour; /* porovnávaná souřadnice */ int porovnat_sour(const void *va, const void *vb) { const struct bod *a = va, *b = vb; return (a->s[por_sour]>b->s[por_sour]) - (a->s[por_sour]s[por_sour]); } /* Najdeme první bod v bloku o daných souřadnicích * pomocí binárního vyhledávání; index tohoto bodu * bude zároveň sloužit jako index celého bloku */ int najit_blok(int bx, int by) { int min = 0, max = n-1; while (min != max) { int i = (min+max)/2; if (body[i].b[1] < by) min = i+1; else if (body[i].b[1] > by) max = i; else if (body[i].b[0] < bx) min = i+1; else max = i; } if (body[min].b[0] == bx && body[min].b[1] == by) return min; return -1; } /* Funkce dostane ukazatele na dvě skupiny bodů, * počet bodů v každé z nich, x-ovou souřadnici přímky * rovnoběžné s osou x, která skupiny rozděluje; vrátí * 1 pokud najde dvojici, která je od sebe vzdálená * méně než 4 a neprotíná kladnou poloosu y, * 2 pokud ji protíná, jinak 0. Pokud je s = 1, počítáme * se souřadnicemi prohozenými oproti popisu. */ unsigned char spojene(struct bod *ba, struct bod *bb, int na, int nb, int s, float x) { static int pred[2][N_MAX], nasl[2][N_MAX]; /* předek a následník daného bodu */ static float zacatek[2][N_MAX]; /* y-ová souřadnice, od níž je * bod rozdělující přímce nejblíž */ struct bod *skup[2] = { ba, bb }; int vel[2] = { na, nb }; float a, b, c, y; for (int t = 0; t < 2; t++) { pred[t][0] = nasl[t][0] = n; zacatek[t][0] = -INFINITY; for (int i = 1; i < vel[t]; i++) { pred[t][i] = i-1; nasl[t][i] = n; for (int j = i-1; ; j = pred[t][j]) { /* najdeme osu spojnice danou rovnicí ax+by+c=0 */ a = skup[t][i].s[s] - skup[t][j].s[s]; b = skup[t][i].s[!s] - skup[t][j].s[!s]; c = - (a*(skup[t][i].s[s]+skup[t][j].s[s])/2) - (b*(skup[t][i].s[!s]+skup[t][j].s[!s])/2); y = -(c+a*x)/b; /* průsečík osy a rozdělující přímky */ if (y < zacatek[t][j]) { /* Jestliže předchozí bod není nikde nejbližší * rozdělující přímce, odstraníme jej, */ pred[t][i] = pred[t][j]; nasl[t][pred[t][i]] = i; } else { /* jinak si zapamatujeme, * odkud je nejbližší současný */ zacatek[t][i] = y; break; } } } } for (int i = 0, j = 0; i < na && j < nb; ) { float dx = skup[0][i].s[s] - skup[1][j].s[s]; float dy = skup[0][i].s[!s] - skup[1][j].s[!s]; if (dx*dx + dy*dy < 16) { if ( /* Jsou li body na různých stranách osy y */ ((skup[0][i].s[0]>0) != (skup[1][j].s[0]>0)) && /* a platí (a_y-b_y) * a_x / (a_x-a_y) < a_y, * tedy směrnice vektoru a-b je menší než * směrnice vektoru a-0 pro kladná a_x * a větší pro záporná a_x, */ ((skup[0][i].s[1]-skup[1][j].s[1]) * (skup[0][i].s[0]) / (skup[0][i].s[0]-skup[1][j].s[0]) < skup[0][i].s[1]) ) return 1; /* protíná jejich spojnice kladnou poloosu y. */ return 2; } /* Posuneme se na další bod buď ve skupině A, nebo B, * podle toho, který se mění dřív */ if (nasl[0][i] != n) { if (nasl[1][j] != n) { if (zacatek[nasl[0][i]] < zacatek[nasl[1][j]]) i = nasl[0][i]; else j = nasl[1][j]; } else i = nasl[0][i]; } else { if (nasl[1][j] != n) j = nasl[1][j]; else return 0; } } return 0; } /* pomocné pole pro dočasné skupiny bodů */ struct bod buf[N_MAX*2]; int bi = 0; /* Funkce hledá hrany mezi skupinami bodů, které mohou být * spojeny oběma typy hran. Vrátí 1 při nalezení pouze * kladnou poloosu y neprotínajících spojení, 2 najde-li * jen ty, které ji protínají, 3, pokud najde obě, * a jinak 0 */ unsigned char spojene_kolem_pocatku(struct bod *a, struct bod *b, int na, int nb) { if (!nb || !na) return 0; if (na == 1 && nb == 1) return spojene (a, b, na, nb, 0, 0); /* Pro jednoduchost zde zvolíme medián směrnic * (tedy spíše pivot, protože to ve většině případů * medián nebude) náhodně, což dopadne dobře v průměrném * případě, jak najít medián spolehlivě v lineárním čase * se dočtete v kuchařce ze druhé série. */ int median; float med_smer; if (na > nb) { median = rand()%na; med_smer = a[median].s[1]/a[median].s[0]; } else { median = rand()%nb; med_smer = b[median].s[1]/b[median].s[0]; } /* Rozdělení na části a rekurze */ int ma = bi; for (int i = 0; i < na; i++) if (med_smer >= a[i].s[1]/a[i].s[0]) buf[bi++] = a[i]; int mb = bi; for (int i = 0; i < na; i++) if (med_smer < a[i].s[1]/a[i].s[0]) buf[bi++] = a[i]; int mc = bi; for (int i = 0; i < nb; i++) if (med_smer >= b[i].s[1]/b[i].s[0]) buf[bi++] = b[i]; int md = bi; for (int i = 0; i < nb; i++) if (med_smer < b[i].s[1]/b[i].s[0]) buf[bi++] = b[i]; unsigned char vysledek = spojene(buf+ma, buf+md, mb-ma, bi-md, 1, 0) | spojene(buf+mb, buf+mc, mc-mb, md-mc, 1, 0) | spojene_kolem_pocatku(buf+ma, buf+mc, mb-ma, md-mc) | spojene_kolem_pocatku(buf+mb, buf+md, mc-mb, bi-md) ; bi = ma; return vysledek; } /* Projde graf bloků a rozhodne, jestli je počátek uvnitř * nějakého polygonu tvořeného hranami cyklu */ bool projit_graf(int a, bool pruseciku) { if (bloky[a].navstiveno) return bloky[a].pruseciku != pruseciku; bloky[a].navstiveno = true; for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { if (!bloky[a].hrany[i][j]) continue; if (bloky[a].hrany[i][j] == 3) return true; if (projit_graf(najit_blok(bloky[a].s[0]+2*j-4, bloky[a].s[1]+2*i-4), pruseciku != (bloky[a].hrany[i][j]&1))) return true; } } return false; } int main(void) { /* Načteme vstup a setřídíme body do skupin podle bloků, * do nichž patří; jednotlivé skupiny pak lexikograficky * podle souřadnic */ float r, poc[2]; scanf("%d%f%f%f", &n, &r, poc, poc+1); for (int i = 0; i < n; i++) { for (int s = 0; s < 2; s++) { scanf("%f", body[i].s+s); body[i].s[s] -= poc[s]; body[i].s[s] /= r/2; body[i].b[s] = (int)(body[i].s[s]/2)*2 + (body[i].s[s] < 0 ? -1 : 1); } } body[n].b[0] = body[n].b[1] = INT_MAX; /* zarážka, která zjednoduší podmínky dále */ qsort(body, n, sizeof(*body), porovnat_bloky); /* Nejprve budeme hledat spojení s dvěma bloky napravo * postupně od každého bloku, takže body uvnitř bloku * potřebujeme mít seřazené podle y-ové souřadnice */ por_sour = 1; for (int i = 0, j = 1; j <= n; j++) { body[j-1].blok = i; if (body[i].b[0] != body[j].b[0] || body[i].b[1] != body[j].b[1]) { bloky[i].s[0] = body[i].b[0]; bloky[i].s[1] = body[i].b[1]; bloky[i].bodu = j-i; qsort(body+i, j-i, sizeof(*body), porovnat_sour); for (int dx = -2; dx; dx++) { int ii = najit_blok(body[i].b[0]+2*dx, body[i].b[1]); if (ii < 0) continue; bloky[i].hrany[2][2+dx] = bloky[ii].hrany[2][2-dx] = spojene(body+i, body+ii, bloky[i].bodu, bloky[ii].bodu, 0, bloky[i].s[0]-1); } i = j; } } /* Teď budeme u každého bloku hledat spojení se zbývajícími * 10 bloky nad ním, k tomu setřídíme body podle x */ por_sour = 0; for (int i = 0, j = 1; j <= n; j++) { if (body[i].b[0] != body[j].b[0] || body[i].b[1] != body[j].b[1]) { qsort(body+i, j-i, sizeof(*body), porovnat_sour); for (int dy = -2; dy; dy++) { for (int dx = -2; dx <= 2; dx++) { int ii = najit_blok(body[i].b[0]+2*dx, body[i].b[1]+2*dy); if (ii < 0) continue; bloky[i].hrany[2+dy][2+dx] = bloky[ii].hrany[2-dy][2-dx] = /* Hledáme-li hranu vedoucí "přes" počátek, */ (bloky[i].s[1] == 1 && dy == -1) && ((bloky[i].s[0] == -1 && dx == 1) || (bloky[i].s[0] == 1 && dx == -1)) ? /* zavoláme speciální funkci, */ spojene_kolem_pocatku( body+i, body+ii, bloky[i].bodu, bloky[ii].bodu) : /* jinak standardní */ spojene(body+i, body+ii, bloky[i].bodu, bloky[ii].bodu, 1, bloky[i].s[1]-1); } } i = j; } } for (int i = 0; i < n; i++) { if (!bloky[i].navstiveno && projit_graf(i, 0)) { printf("Nelze se obhájit.\n"); return 0; } } printf("Je možné se obhájit.\n"); return 0; }