#include #include #include #include #include using namespace std; struct Edge; struct Vertex { double x, y; Edge *neighbors[2]; bool operator <(const Vertex &other) const { return (y < other.y || (y == other.y && x < other.x)); } // Nechť [0] je ta hrana, co vede více doleva. void order(); }; struct Edge { Edge(Vertex *v1, Vertex *v2) { neighbors[0] = v1; neighbors[1] = v2; // Zařídíme, aby v [0] byl ten horní vrchol. if (v1->y > v2->y) swap(neighbors[0], neighbors[1]); v1->neighbors[0] = this; v2->neighbors[1] = this; } Vertex *neighbors[2]; // Sklon hrany. 0 je přímo dolů, čím větší, tím více doprava. double direction() const { double height = neighbors[1]->y - neighbors[0]->y; // Abychom nedělili nulou if (height <= 0) height = DBL_EPSILON; return (neighbors[1]->x - neighbors[0]->x) / height; } // Jak moc vpravo je ta úsečka v dané výšce? double x(double y) const { double height = y - neighbors[0]->y; return neighbors[0]->x + direction() * height; } }; void Vertex::order() { if (neighbors[0]->direction() > neighbors[1]->direction()) swap(neighbors[0], neighbors[1]); } // Aktuální výška. Používá se při porovnávání hran, která je víc vlevo v danou chvíli. double height; // Nejlepší úsečka, co známe. double bestLength, bestX, bestY; struct Segment { Segment(Edge *left, Edge *right) { ends[0] = left; ends[1] = right; } Edge *ends[2]; // Jedna úsečka je více nalevo než druhá, pokud je její pravá hrana více nalevo // Ono je jedno, který konec porovnáváme (nepřekrývají se), jen v tomto případě // nemusíme řešit zaokrouhlovací chyby u upper_bound z C++. // // Porovnává ve výšce height. bool operator <(const Segment &other) const { // Trik s DBL_EPSILON zaručí, že ty, co se rovnají sem nespadnou. return ends[1]->x(height) + DBL_EPSILON * 10 < other.ends[1]->x(height); } // Zjistí, jestli úsečka obsahuje bod. Opět, uvažujeme ve výšce height. bool contains(const Vertex& v) const { // Trik s DBL_EPSILON o kousíček prodlouží úsečku, čímž řeší zaokrouhlovací problémy // u doublu v počítači. return (ends[0]->x(v.y) - DBL_EPSILON * 10 <= v.x && v.x <= ends[1]->x(v.y) + DBL_EPSILON); } // Podívá se, jestli náhodou není tato úsečka delší, než nejdelší známá. Pokud // je. tak uloží. // // Porovnává ve výšce height. void candidate() const { double length = ends[1]->x(height) - ends[0]->x(height); if (length >= bestLength) { bestX = ends[0]->x(height); bestY = height; bestLength = length; } } }; vector vertices; // Živé úsečky. Ten "set" je jen vyhledávací strom z knihoven C++. set segments; bool less(Vertex* _1, Vertex* _2) { return *_1 < *_2; } int main() { size_t n; cin >> n; // Načtení vcholů for (size_t i = 0; i < n; ++ i) { // Ano, tu paměť nikdo nevrací. Vrátí se na konci programu sama. Vertex *v(new Vertex); cin >> v->x >> v->y; vertices.push_back(v); } // Nagenerování hran mezi nimi for (size_t i = 0; i < n; ++ i) new Edge(vertices[i], vertices[(i + 1) % n]); for (size_t i = 0; i < n; ++ i) vertices[i]->order(); // Seřadíme vrcholy odshora dolů (uvažujeme, že nahoře jsou menší y, jako na monitoru) sort(vertices.begin(), vertices.end(), ::less); height = vertices[0]->y; // Projdeme všechny vrcholy a zpracujeme rozborem případů. for (size_t i = 0; i < n; ++ i) { // Jestli hrana tohoto vrcholu jde z něj nahoru. bool orientation[2]; for (size_t j = 0; j < 2; ++ j) // To se pozná tak, že tento vrchol je její spodní, tedy [1] orientation[j] = vertices[i]->neighbors[j]->neighbors[1] == vertices[i]; // Uložíme aktuální výšku, pro porovnávání. height = vertices[i]->y; // Rozeberme si případy, jak ten vrchol vypadá. if (orientation[0] && orientation[1]) { // Obě hrany vedou nahoru. Buď sloučíme dvě úsečky, nebo jednu zrušíme. // Falešná úsečka, na nalezení správného prvku ve stromu. Segment position(vertices[i]->neighbors[0], vertices[i]->neighbors[1]); // Funkce upper_bound by měla dát tu úsečku napravo od tohoto bodu, pokud // existuje. set::iterator right(segments.upper_bound(position)); set::iterator left(right); if (left != segments.begin()) // Nejsme na začátku, smíme doleva -- left; if (left != right && right != segments.end() && left->contains(*vertices[i]) && right->contains(*vertices[i])) { // Levá i pravá se dotýká bodu, slučujeme Segment segment(left->ends[0], right->ends[1]); segment.candidate(); segments.erase(left); segments.erase(right); segments.insert(segment); } else { // Odstraňujeme úsečku. Bude to ta vlevo (díky tomu, že upper_bound // vrací ostře větší a tady už je ta úsečka nulové délky) left->candidate(); segments.erase(left); } } else if (!orientation[0] && !orientation[1]) { // Obě hrany vedou dolů. Buď dělíme, nebo přidáváme. // Zkusíme udělat úsečku v tomto bodě. Segment position(vertices[i]->neighbors[0], vertices[i]->neighbors[1]); // Zkusíme najít úsečku úsečku, co začíná někde za tímto bodem a posuneme se o 1 doleva. // Strom set obsahuje i jeden falešný prvek, který je na konci, takže je to OK i u // poslední úsečky. Na začátku si musíme dát trochu pozor. set::iterator segment(segments.upper_bound(position)); if (segment != segments.begin()) -- segment; if (segment != segments.end() && segment->contains(*vertices[i])) { // Tuto úsečku dělíme na dvě Segment left(segment->ends[0], vertices[i]->neighbors[0]); Segment right(vertices[i]->neighbors[1], segment->ends[1]); segment->candidate(); segments.erase(segment); segments.insert(left); segments.insert(right); } else { // Přidáme novou úsečku. position.candidate(); segments.insert(position); } } else { // Jeden vede nahoru a jeden dolů. Zjištěme si, který nahoru. size_t upper = orientation[1]; // Nalezněme správnou úsečku ve stromu. Segment position(vertices[i]->neighbors[0], vertices[i]->neighbors[1]); // Tohle najde požadovanou úsečku, pokud jsme na levé straně, nebo // jednu doprava od ní, pokud jsme na pravém konci. set::iterator segment(segments.upper_bound(position)); bool rightSide(false); if (segment == segments.end() || !segment->contains(*vertices[i])) { rightSide = true; -- segment; } // Vyzkoušíme tuto úsečku. segment->candidate(); // Objekt set nedovolí měnit prvky, musíme udělat nový a nahradi. Segment replacement = *segment; // Vyměníme jednu stranu úsečky. Tu správnou. Chceme tu dolní z vrcholu. replacement.ends[rightSide] = vertices[i]->neighbors[1 - upper]; // A vyměnit. segments.erase(segment); segments.insert(replacement); } } // Už jen vypíšeme tu nejdelší úsečku. cout << "Nejdelší úsečka je dlouhá " << bestLength << " a začíná na pozici [" << bestX << ", " << bestY << "]" << endl; return 0; }