#include #include #define debug(...) fprintf(stderr, __VA_ARGS__) //#define debug(...) // Souřadnice vektoru či bodu typedef struct { double c[2]; } vektor; typedef struct { vektor pocatek; vektor smer; } poloprimka; #define MAXN 1000 vektor V[MAXN]; int start, end; // První a poslední index ve V, který obsahuje platný bod. vektor P, u; // Počátek a směrový vektor `p' poloprimka p; int kraj1, kraj2; // Krajní body bin. vyhledávání int wrap(int idx) { while (idx < start) idx += (end - start + 1); while (idx > end) idx -= (end - start + 1); return idx; } vektor soucet(vektor a, vektor b) { vektor r; r.c[0] = a.c[0] + b.c[0]; r.c[1] = a.c[1] + b.c[1]; return r; } vektor nasobek(vektor v, double alfa) { vektor r; r.c[0] = alfa * v.c[0]; r.c[1] = alfa * v.c[1]; return r; } vektor rozdil(vektor a, vektor b) { return soucet(a, nasobek(b, -1)); } // Vrátí z-ovou složku vektorového součinu a×b. Ostatní jsou vždy nulové. double soucin(vektor a, vektor b) { return a.c[0]*b.c[1] - a.c[1]*b.c[0]; } // Vrátí: // (-1)... b leží napravo od q // 0 ... b leží na q // 1 ... b leží nalevo od q int poloha_bodu(poloprimka q, vektor B) { double tmp = soucin(q.smer, rozdil(B, q.pocatek)); if (tmp == 0) return 0; else if (tmp > 0) return 1; else return -1; } void nacti_vstup() { int n; scanf("%d", &n); start = 0; end = n - 1; for (int i = 0; i < n; i++) scanf("%lf %lf", &V[i].c[0], &V[i].c[1]); scanf("%lf %lf %lf %lf", &P.c[0], &P.c[1], &u.c[0], &u.c[1]); p.pocatek = P; p.smer = u; } // První fáze -- nalezení krajních bodů pro binární vyhledávání. int najdi_krajni() { // Dokud máme alespoň čtyři body, zkoušíme půlit. while (end - start + 1 >= 4) { int m = (start + end + 1) / 2; int p1 = poloha_bodu(p, V[start]); int p2 = poloha_bodu(p, V[m]); debug("najdi_krajni(): %d[%d]..%d[%d]..%d\n", start, p1, m, p2, end); // TODO ošetřit, když p1 && p2 = 0 if (p1 == p2) { vektor S = nasobek(soucet(V[start], V[m]), 0.5); poloprimka o = {P, rozdil(S, P)}; // Určení X a Y // Poloha `p' (reprezentované bodem P+u) vůči `o' int poloha_p = poloha_bodu(o, soucet(P, u)); int x, y; if (poloha_bodu(o, V[start]) == poloha_p) { x = start; y = m; } else { x = m; y = start; } // Nalezení W poloprimka PX = { P, rozdil(V[x], P) }; int w; if (poloha_bodu(PX, V[wrap(x-1)]) == -poloha_p) { w = wrap(x-1); } else { w = wrap(x+1); } if (w < m) { // zahodíme V[1]..V[m-1] // -> musíme přesunout V[0] na místo V[m-1], aby zachované // vrcholy tvořily souvislý úsek V[m-1] = V[0]; start = m - 1; } else { // zahodíme V[m+1]..V[n-1] end = m; } } else { kraj1 = start; kraj2 = m; return 1; } } return 0; } // Binárně vyhledá hranici mezi p-levými a p-pravými vrcholy v intervalu [a,b] // (braném po směru hodinových ručiček). int najdi_hranici(int x, int y, int *h1, int *h2) { debug("najdi_hranici(): x=%d, y=%d\n", x, y); int a = 0, b = abs(y - x); // Binární vyhledávání končí, když má aktivní úsek právě dva body. // Mezi nimi pak leží levo-pravá hranice. while (b > a + 1) { int m = (a + b) / 2; int pa = poloha_bodu(p, V[wrap(x + a)]); int pb = poloha_bodu(p, V[wrap(x + b)]); int pm = poloha_bodu(p, V[wrap(x + m)]); debug(" %d[%d] .. %d[%d] .. %d[%d]\n", wrap(x+a), pa, wrap(x+m), pm, wrap(x+b), pb); if (pa == pm) a = m; else b = m; } *h1 = wrap(x + a); *h2 = wrap(x + b); } // Průsečík polopřímky $p$ s _přímkou_ $q$ // http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/565282#565282 int najdi_prusecik(poloprimka p, poloprimka q, vektor *prusecik) { // Hodnota parametru $t$, pro kterou (p.pocatek + t * p.smer) je hledaným průsečíkem double t = soucin(rozdil(q.pocatek, p.pocatek), q.smer) / soucin(p.smer, q.smer); if (t < 0) return 0; // Průsečík ve špatné části polopřímky *prusecik = soucet(p.pocatek, nasobek(p.smer, t)); return 1; } // Vypíše průsečík $p$ s hranou ab, pokud existuje (je na správné straně od P) void vypis_prusecik(int a, int b) { vektor prusecik; poloprimka q = {V[a], rozdil(V[b], V[a])}; // přímka AB debug("Prusecik: %d-%d\n", a, b); if (najdi_prusecik(p, q, &prusecik)) printf("%lf %lf\n", prusecik.c[0], prusecik.c[1]); } int main() { nacti_vstup(); if (najdi_krajni()) { debug("Nalezeny krajní body: %d %d. Zbývají body: %d-%d.\n", kraj1, kraj2, start, end); int h1, h2, h3, h4; najdi_hranici(kraj1, kraj2, &h1, &h2); najdi_hranici(kraj2, kraj1, &h3, &h4); vypis_prusecik(h1, h2); vypis_prusecik(h3, h4); } else { debug("Nalezeny krajní body. Zbývají body: %d-%d.\n", start, end); for (int v = start; v <= end; v++) { // Protíná se hrana V[v]V[v+1] s p? if (poloha_bodu(p, V[v]) != poloha_bodu(p, V[wrap(v+1)])) { vypis_prusecik(v, wrap(v+1)); } } } return 0; }