#include #include #include #include #include using namespace std; typedef struct { // Meze int x0, x1, y0, y1; // Zvolené místo int x, y; } tower_2d; // Řešení jednorozměrné verze: typedef struct { // Meze int x0, x1; // Zvolené místo int x; } tower_1d; tower_1d* _TOWERS; // Porovnávací funkce na indexy věží - třídí podle x0 nebo x1 enum CompareTowersBy { BY_MIN, BY_MAX_INVERSE }; class CompareTowers1D { private: vector towers; CompareTowersBy by; public: CompareTowers1D(vector _towers, CompareTowersBy _by) { towers = _towers; by = _by; } bool operator() (int _a, int _b) { switch (by) { case BY_MIN: return (towers[_a].x0 < towers[_b].x0); case BY_MAX_INVERSE: return (towers[_a].x1 > towers[_b].x1); default: assert(false); } } }; // Porovnávací funkce na indexy věží - třídí podle x1 bool solve_towers_1d(vector &towers) { vector indexes(towers.size()); for (unsigned int i = 0; i < towers.size(); i++) indexes[i] = i; // Setřídím věže podle minima intervalu. sort(indexes.begin(), indexes.end(), CompareTowers1D(towers, BY_MIN)); unsigned int current_index = 0; vector heap; // Přiřadím věžím v setříděném pořadí sloupečky. int last_used = -1; for (unsigned int i = 0; i < towers.size(); i++) { // Přidám do haldy všechny věže, které teď budu moct umístit. Navíc v haldě musí být aspoň jedna věž. while (current_index < indexes.size() && (towers[indexes[current_index]].x0 <= last_used + 1 || heap.begin() == heap.end())) { heap.push_back(indexes[current_index]); push_heap(heap.begin(), heap.end(), CompareTowers1D(towers, BY_MAX_INVERSE)); current_index++; } // Vezmu teď první věž na haldě. int j = heap[0]; pop_heap(heap.begin(), heap.end(), CompareTowers1D(towers, BY_MAX_INVERSE)); heap.pop_back(); tower_1d* t = &towers[j]; if (last_used < t->x0) { t->x = t->x0; last_used = t->x; } else if (last_used < t->x1) { t->x = last_used + 1; last_used = t->x; } else { // Věž nejde nikam přiřadit. return false; } } return true; } bool solve_towers_2d(vector &towers) { // Nejdříve vyřeš v ose X. vector tmp(towers.size()); for (unsigned int i = 0; i < towers.size(); i++) { tmp[i].x0 = towers[i].x0; tmp[i].x1 = towers[i].x1; } if (!solve_towers_1d(tmp)) { return false; } for (unsigned int i = 0; i < towers.size(); i++) { towers[i].x = tmp[i].x; } // Teď vyřeš v ose Y. for (unsigned int i = 0; i < towers.size(); i++) { tower_1d* t = &tmp[i]; t->x0 = towers[i].y0; t->x1 = towers[i].y1; } if (!solve_towers_1d(tmp)) { return false; } for (unsigned int i = 0; i < towers.size(); i++) { towers[i].y = tmp[i].x; } // OK, máme řešení. return true; } int main(void) { // Očekávaný formát vstupu: // (počet věží) // Pro každou věž meze obdélníka: // (X0) (X1) (Y0) (Y1) // Formát výstupu: // Pro každou věž souřadnice: // (X) (Y) int N; int i; cin >> N; vector towers(N); for (i = 0; i < N; i++) { tower_2d* t = &towers[i]; cin >> t->x0 >> t->x1 >> t->y0 >> t->y1; } if (!solve_towers_2d(towers)) { cout << "Řešení neexistuje." << endl; } else { for (i = 0; i < N; i++) { cout << towers[i].x << " " << towers[i].y << endl; } } return 0; }