#include #include #define MAX_N 1000000 int A[MAX_N], B[MAX_N], C[MAX_N]; int N; /* * Porovná směrnice A[i] / B[i] a vrátí true, pokud směrnice * přímky p je menší nez směrnice přímky q. Abychom nemuseli * převádět celá čísla na double a ztrácet tím přesnost, upravíme * zkoumanou nerovnost A[p] / B[p] < A[q] / B[q] do tvaru, kde * se pouze násobí. Při násobení je třeba být opatrný na přetečení. * Poznamenejme, že přímka s B[i] = 0 bude zařazena na konec. */ bool porovnej_smernice(int p, int q) { return (long long)A[p] * B[q] < (long long)A[q] * B[p]; } // Indexy přímek uspořádané vzestupně podle jejich směrnic. int primky[MAX_N]; /* * Hledáme průsečík přímek * p: A[p] * x + B[p] * y + C[p] = 0 * q: A[q] * x + B[q] * y + C[q] = 0 * Řešíme soustavu dvou lineárních rovnic o dvou neznámých. */ void prusecik_primek(int p, int q, double &x, double &y) { x = (double)(B[q] * C[p] - B[p] * C[q]) / (B[q] * A[p] - B[p] * A[q]); y = (double)(A[q] * C[p] - A[p] * C[q]) / (A[q] * B[p] - A[p] * B[q]); } // Průsečíky přímek sousedících v cyklickém uspořádání. double prusecik_X[MAX_N], prusecik_Y[MAX_N]; /* * Následuje standardní algoritmus na výpočet konvexního obalu bodů v rovině. * Nejprve uspořádáme všechny body vzestupně podle souřadnice x. * Poté je procházíme v tomto pořadí a průběžně tvoříme horní a dolní * půl-obaly a nakonec sloučíme obě části do jednoho obalu. * * Funkci v programu volame jedinkrát, a proto pro jednoduchost načítáme * vstup i ukládáme výstup do globálních polí. * Vstup: prusecik_X, prusecik_Y * Výstup: obal délky delka_obalu obsahuje indexy průsečíků */ int obal[MAX_N], delka_obalu; int horni[MAX_N], delka_horni, dolni[MAX_N], delka_dolni; /* Primárně porovnáváme podle y, sekundárně podle x. */ bool porovnej_pruseciky(int a, int b) { if (prusecik_X[a] != prusecik_X[b]) return prusecik_X[a] < prusecik_X[b]; return prusecik_Y[a] < prusecik_Y[b]; } int pruseciky[MAX_N]; /* Třetí složka vektorového součinu vektoru PQ a PR. */ long long vektorovy_soucin(int P, int Q, int R) { return (prusecik_X[Q] - prusecik_X[P]) * (prusecik_Y[R] - prusecik_Y[P]) - (prusecik_Y[Q] - prusecik_Y[P]) * (prusecik_X[R] - prusecik_X[P]); } void konvexni_obal() { for (int i = 0; i < N; ++i) pruseciky[i] = i; std::sort(pruseciky, pruseciky + N, porovnej_pruseciky); delka_horni = delka_dolni = 0; for (int i = 0; i < N; ++i) { while ( delka_horni > 1 && vektorovy_soucin(i, horni[delka_horni - 1], horni[delka_horni - 2]) <= 0 ) delka_horni--; while ( delka_dolni > 1 && vektorovy_soucin(i, dolni[delka_dolni - 1], dolni[delka_dolni - 2]) >= 0 ) delka_dolni--; horni[delka_horni++] = i; dolni[delka_dolni++] = i; } delka_obalu = 0; for (int i = 0; i < delka_horni; ++i) obal[delka_obalu++] = horni[i]; for (int i = delka_dolni - 2; i >= 1; --i) obal[delka_obalu++] = dolni[i]; } int main(int argc, char *argv[]) { // Načteme vstup. scanf("%d", &N); for (int i = 0; i < N; ++i) scanf("%d%d%d", A + i, B + i, C + i); // Uspořádáme přímky vzestupně dle jejich směrnic. for (int i = 0; i < N; ++i) primky[i] = i; std::sort(primky, primky + N, porovnej_smernice); // Spočítáme průsečíky každých dvou přímek sousedních směrnic. for (int i = 0; i < N - 1; ++i) prusecik_primek(i, i + 1, prusecik_X[i], prusecik_Y[i]); prusecik_primek(N - 1, 0, prusecik_X[N - 1], prusecik_Y[N - 1]); // Spočítáme kondexní obal. konvexni_obal(); // Vypíšeme výsledek. for (int i = 0; i < delka_obalu; ++i) printf("%.6lf %.6lf\n", prusecik_X[obal[i]], prusecik_Y[obal[i]]); return 0; }