Zadanie
Ako každý vie, Meky Žbirka miluje psíkov. Väčšinou ich necháva voľne vypustených vo svojej záhradke v Slovakistane, ale kvôli veľkému nárastu kriminality a krádeží v krajine sa uchýlil k bezpečnejšej alternatíve. Každého psa Meky priviazal k jednej z dvoch gigantických, kompletne čiernych železných tyčí, ktoré mu trčali v záhrade.
Psom sa tento nápad zo začiatku nepáčil. Časom si na to však až tak zvykli, že sa spolu úplne prestali stýkať psíkovia, ktorí boli priviazaní k rôznym tyčiam. Dokonca si podľa toho aj zmenili farbu srsti – pri jednej tyčí na bielu a pri druhej na čiernu.
Po dlhšej dobe však psov omrzelo naďalej prechádzať okolo tyče, aby sa stretli so svojimi kamarátmi. Vymysleli si teda nový spôsob navštevovania. Pes len strašne silno vyskočí, a keďže je k tyči priviazaný, spraví veľký polkruh vzduchom a dopadne presne na opačné miesto na druhej strane tyče. Asi takto:
Psíkovia sú veľmi spoločenskí, preto boli od začiatku prezieravo rozostavení tak, aby každý z nich mohol týmto pohybom stretnúť na opačnej strane tyče nejakého psíka rovnakej farby.
Teraz dostal Meky úžasný nápad. Odfotí svojich psíkov v záhradke svojím novým čierno-čierným foťákom. Nedošlo mu však, že na takejto fotke sa stratí farba psov a dokonca aj pozícia kompletne čiernych tyčí. Teraz by sa však chcel pochváliť ostatným legendárnym spevákom a ukázať im jeho psov na fotke v plnej kráse aj s tyčami, ku ktorím sú priviazaní. Keďže Meky je spevák a nebude sa zaneprázdňovať takými trápnymi úlohami, prischla úloha vám.
Úloha
Psíkov vieme interpretovať ako body v rovine. Z Mekyho fotky vieme zistiť pozície jednotlivých psov, avšak nie pozíciu tyčí, ku ktorým sú priviazaní. Vieme, že pes je buď čierny alebo biely a všetci psíkovia jednej farby sú spolu priviazaní k jednej tyči, ktorá je taktiež bodom v rovine. Zároveň vieme, že pre každého psa existuje na opačnej strane tyče (tej, ku ktorej je priviazaný) pes rovnakej farby. Tyč sa môže nachádzať na pozícií psa. V takom prípade, ak je k nej daný pes priviazaný, je sám sebe na opačnej strane tyče.
Pre zadané pozície psov určite, či existujú také dve tyče a rozdelenie psov do farieb, ktoré spĺňajú podmienky uvedené vyššie.
Formát vstupu
V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 300\)) udávajúce počet psov na fotke.
Na \(i\)-tom z nasledujúcich \(n\) riadkov sú \(2\) celé čísla \(x_i, y_i\) \((|x_i|,|y_i|\leq 10^9)\) - \(x\) a \(y\) súradnica \(i\)-teho psa. Žiadna z dvojíc sa na vstupe nevyskytne viac krát - psy sú na rôznych miestach.
Formát výstupu
V prípade, že neexistujú dve tyče a rozdelenia psov do farieb, ktoré
spĺňajú podmienky zadania, vypíšte na jediný riadok výstupu
zbirka dozbirkoval.
V opačnom prípade vypíšte \(3\) riadky.
- Na prvom riadku
zbirka je kral. - Na druhom riadku štyri čísla oddelené medzerami \(tx_0\) \(ty_0\) \(tx_1\) \(ty_1\) - súradnice prvej a druhej tyče v poradí (\(x\) a \(y\)).
- Na treťom riadku pre každého psa vypíšte bez medzier jedno číslo, buď \(0\), ak má byť priviazaný k tyči \(0\) alebo \(1\) ak má byť priviazaný k tyči \(1\).
Ak existuje viac riešení, môžete vypísať ľubovoľné z nich. Súradnice tyčí vypíšte s dostatočnou presnosťou za desatinnou čiarkou.
Hodnotenie
| Sada | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| \(1 \leq n \leq\) | \(15\) | \(30\) | \(70\) | \(70\) | \(300\) | \(300\) |
| \(0 \leq \|x_i\|, \|y_i\| \leq\) | \(100\) | \(100\) | \(1000\) | \(10^9\) | \(10^9\) | \(10^9\) |
| dodatočné obmädzenia | \(x_i=y_i\) |
Príklady
Input:
6
1 1
2 2
4 4
5 5
10 -5
10 -100Output:
zbirka je kral
3 3 10 -52.5
000011Input:
5
1 1
5 5
10 -5
10 -100
100000 10000Output:
zbirka dozbirkovalJedna tyč musí byť medzi 1. a 2. psom, jedna medzi 3. a 4. a pre 5. už nič nezostane.
Vymýšľanie a vylepšovanie bruteforce riešení prenecháme čitateľovi, ako tréning. My skočíme rovno k základným pozorovaniam a postupom.
Počas vzoráku budeme hovoriť o obraze psa, cez nejakú tyč - to bude taký pes, ktorý je presne na opačnej strane tyče (nemusí byť nutne rovnakej farby). Ak takýto pes neexistuje, tak budeme hovoriť, že pes nemá obraz cez danú tyč.
Iba určíme farby
Predstavme si, že by nám niekto povedal, kde sa nachádzajú tyče. Skúsme teraz nájsť rýchly algoritmus, ktorým rozdelíme psíkov na bielych a čiernych, alebo prehlásime, že to nie je možné.
Vyberieme jednu tyč a prehlásime, že všetci psíkovia k nej priviazaní budú čierny. Túto tyč nazveme čiernou, druhú tyč nazveme bielou. Ani jedna farba nie je ničím špeciálna a môžme ich hocikedy vymeniť. Nám sa jednoduchšie bude pracovať s konkrétnou farbou, preto sme si vybrali napríklad čiernu.
Ak máme psa, ktorý nemá obraz cez čiernu tyč, znamená to, že pokiaľ má existovať riešenie, musí v ňom byť tento pes biely. Takýchto psov budeme volať povinne bieli.
Zoberme všetkých povinne bielych psov. Každý z nich musí mať obraz cez bielu tyč. Každý z týchto obrazov musí byť tiež biely pes, a to aj ak nie je povinne biely.
Vyberme si niektorého povinne bieleho psa \(x\) a jeho obraz, nech je to pes \(i\). Pes \(i\) je vždy jednoznačne určený, lebo nemôžu byť dvaja psi na jednom mieste. Vieme, že pes \(i\) je biely, inak by \(x\) nemal obraz cez bielu tyč. Pokiaľ má pes \(i\) obraz cez čiernu tyč, nech je to pes \(j\), musí aj pes \(j\) byť biely. Prečo? Ak by bol pes \(j\) čierny, musel by aj jeho obraz cez čiernu tyč – pes \(i\) – byť čierny, čo je spor.
V zásade vždy keď prehlásime nejakého psa za bieleho, musíme skontrolovať:
- či má nejaký obraz cez bielu tyč - ak by nemal, táto voľba tyčí je nesprávna
- či má nejaký obraz cez čiernu tyč - ak áno, tento obraz tiež prehlásime za biely a skontrolujeme ho.
Na začiatku prehlásime za bielych všetkých povinne bielych, teda takých, ktorí nemajú obraz cez čiernu tyč.
Tento algoritmus má časovú zložitosť \(O(n)\) - iba pre každého psa skontrolujeme zopár obrazov.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define For(i, a, n) for (ll i = a; i < (ll)n; i++)
#define all(x) begin(x), end(x)
#define sz(x) (ll) x.size()
ll n;
vector<pll> psy;
map<pll, ll> pozicie; // pre poziciu aky je na nej pes
pll mid(pll a, pll b) { // stred medzi bodmi a, b
// ked vsetko hned na zaciatku prenasobim 2
// nemusim sa babrat s floatami
return {(a.first + b.first) / 2, (a.second + b.second) / 2};
}
pll image(pll a, pll s) {
// obraz bodu a cez s
return {s.first - (a.first - s.first), s.second - (a.second - s.second)};
}
bool solve(pll mid_black, pll mid_white) {
// predpocitam si obrazy cez cierny a biely stred
vector<pll> sus(n, {-1, -1});
For(i, 0, n) {
pll image_black = image(psy[i], mid_black), image_white = image(psy[i], mid_white);
if (pozicie.count(image_black)) sus[i].first = pozicie[image_black];
if (pozicie.count(image_white)) sus[i].second = pozicie[image_white];
// ak nemam ani jeden obraz, mozem skoncit
if (sus[i].first == -1 && sus[i].second == -1) return false;
}
queue<ll> spracuj;
// ak nemam suseda v ciernom, som povinne biely
For(i, 0, n) if (sus[i].first == -1) spracuj.push(i);
vector<ll> solved(n);
vector<ll> white;
while (!spracuj.empty()) { // spracujem postupne bielych,
// mozno priadm aj nejakych dalsich
ll t = spracuj.front();
spracuj.pop();
if (solved[t]) continue;
solved[t] = true;
white.push_back(t);
if (sus[t].first != -1) { // davam sa do white,
// takze moj obraz v black musi byt white
spracuj.push(sus[t].first);
}
if (sus[t].second != -1) { // som white, takze musim mat obraz vo white
// ten tiez musim niekedy spracovat
spracuj.push(sus[t].second);
} else
return false; // mal by som mat obraz vo white, ale nemam
}
vector<ll> ans(n);
for (auto i : white) ans[i] = 1;
cout << setprecision(1) << fixed;
cout << "zbirka je kral" << endl;
cout << mid_black.first / (double)2 << ' ' << mid_black.second / (double)2 << ' '
<< mid_white.first / (double)2 << ' ' << mid_white.second / (double)2 << endl;
for (auto i : ans) cout << i;
cout << endl;
return true;
}Pomocou tohoto algoritmu teraz budeme testovať, či je dané rozostavenie tyčí prípustné.. Týchto rozostavení je však veľa, preto si ukážeme, ako odstrániť niektoré, ktoré nemajú šancu byť správne.
Prvé zaujímavé riešenie
Môžeme si všimnúť, že na to, aby nejaká tyč mala šancu byť v správnom riešení, musia existovať nejakí – nie nutne rôzni – psi \(i\) a \(j\), ktorí sa na seba cez túto tyč zobrazia (teda tyč je v strede medzi nimi). Ak by sme v nejakom riešení vybrali tyč nesplňujúcu túto podmienku, určite by sme k nej nemohli priviazať žiadneho psa, lebo nemá obraz cez túto tyč. Preto môžeme túto tyč umiestniť hocikam inam a dostaneme rovnako dobré riešenie. Jednou z možností, kam ju umiestniť, je to isté miesto, na ktorom je druhá tyč tohto riešenia. Týmto spôsobom sme určite dodržali podmienku vyššie. K druhému stĺpu totiž musel byť priviazaný nejaký pes a jeho obraz, teda tento stĺp je uprostred nejakých dvoch psov.
Pre každú tyč teda máme \(O(n^2)\) možností, kde môže byť umiestnená. Pre dve tyče spolu dostávame \(O(n^4)\) možností, čo spolu s kontrolou platnosti dáva zložitosť \(O(n^5)\).
Máme príliš veľa voľnosti
Na to, aby sme mali správne riešenie, musí byť každý pes priviazaný k nejakej tyči. Toto platí aj pre psíka s číslom \(0\). Aspoň jedna z tyčí teda musí byť taká, že psík \(0\) má cez ňu obraz.
Tým sa nám zmenšuje počet možností, ktoré musíme kontrolovať. Máme \(n\) možností na prvú tyč, tak, aby bola v strede medzi psíkom \(0\) a nejakým ďalším psíkom (kľudne aj psíkom \(0\)). Druhú tyč budeme umiestňovať rovnako ako doteraz, teda na jej pozície máme \(O(n^2)\) možností.
Každú z týchto možností skontrolujeme v čase \(O(n)\), dostávame teda \(O(n^4)\) riešenie.
Všimnime si ešte, že pes \(0\) nemusí byť v riešení priviazaný k prvej tyči. Zjavne však ku niektorej tyči priviazaný bude, teda v konečnom dôsledku len neskúšame možnosti, ktoré určite fungovať nebudú.
Zopakujeme starú myšlienku
Ešte stále skúšame niektoré možnosti zbytočne.
Zafixujeme si opäť psa \(0\) a povedzme, že bude čiernej farby. Vyskúšame všetky možnosti, na ktorého psa sa pes \(0\) zobrazí. To nám zadá pozíciu čiernej tyče. Podobne ako v prvom odseku vieme teraz zostrojiť množinu psov, ktorí sú povinne bieli.
Teraz použijeme myšlienku z predchádzajúceho odseku. Pes \(0\) nebol ničím špeciálny. My máme množinu povinne bielych a vieme, že každý z nich musí mať obraz cez bielu tyč. Opäť si môžeme vybrať ľubovoľného povinne bieleho psa – napríklad s najmenším číslom – a skúšať len stĺpy, ktoré sú v strede medzi ním a nejakým ďalším psom. Týmto spôsobom máme aj na pozíciu druhej tyče len \(O(n)\) možností.
Máme teda \(n\) možností na pozíciu čiernej tyče a pre každú z nich \(O(n)\) možností na pozíciu bielej. Spolu máme \(O(n^2)\) možností a pre každú vyskúšame v \(O(n)\), či vyhovuje. Tým dostávame optimálnu zložitosť \(O(n^3)\).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define For(i, a, n) for (ll i = a; i < (ll)n; i++)
#define all(x) begin(x), end(x)
#define sz(x) (ll) x.size()
ll n;
vector<pll> psy;
map<pll, ll> pozicie; // pre poziciu aky je na nej pes
pll mid(pll a, pll b) {
return {(a.first + b.first) / 2, (a.second + b.second) / 2};
}
pll image(pll a, pll s) {
return {s.first - (a.first - s.first), s.second - (a.second - s.second)};
}
bool solve(pll mid_black, pll mid_white) {
// predpocitam si obrazy cez cierny a biely stred
vector<pll> sus(n, {-1, -1});
For(i, 0, n) {
pll i1 = image(psy[i], mid_black), i2 = image(psy[i], mid_white);
if (pozicie.count(i1)) sus[i].first = pozicie[i1];
if (pozicie.count(i2)) sus[i].second = pozicie[i2];
// ak nemam ani jeden obraz, mozem skoncit
if (sus[i].first == -1 && sus[i].second == -1) return false;
}
queue<ll> q;
// ak nemam suseda v ciernom, musim byt biely
For(i, 0, n) if (sus[i].first == -1) q.push(i);
vector<ll> solved(n);
vector<ll> white;
while (!q.empty()) { // spracujem postupne bielych,
// mozno priadm aj nejakych dalsich
ll t = q.front();
q.pop();
if (solved[t]) continue;
solved[t] = true;
white.push_back(t);
if (sus[t].first != -1) { // davam sa do white,
// takze moj obraz v black musi byt white
q.push(sus[t].first);
}
if (sus[t].second != -1) { // som white, takze musim mat obraz vo white
// ten tiez musim niekedy spracovat
q.push(sus[t].second);
} else
return false; // mal by som mat obraz vo white, ale nemam
}
vector<ll> ans(n);
for (auto i : white) ans[i] = 1;
cout << setprecision(1) << fixed;
cout << "zbirka je kral" << endl;
cout << mid_black.first / (double)2 << ' ' << mid_black.second / (double)2 << ' '
<< mid_white.first / (double)2 << ' ' << mid_white.second / (double)2 << endl;
for (auto i : ans) cout << i;
cout << endl;
return true;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n;
psy.resize(n);
for (auto& i : psy) {
cin >> i.first >> i.second;
i.first = i.first * 2; // ked hodnoty vynasobim 2,
i.second = i.second * 2; // nemusim pouzivat double na delenie
pozicie[i] = sz(pozicie);
}
For(j, 0, n) {
pll mid_black = mid(psy[0], psy[j]);
ll nejaky_biely = -1;
// najdem aspon nejakeho bieleho
For(i, 0, n) if (!pozicie.count(image(psy[i], mid_black))) nejaky_biely = i;
if (solve(mid_black, mid_black)) return 0; // mozem mat obe tyce na jednom mieste
if (nejaky_biely != -1) {
For(k, 1, n) { // moj biely sa musi na nieco zobrazit,
// tak vyskusam vsetky moznosti
pll mid_white = mid(psy[nejaky_biely], psy[k]);
if (solve(mid_black, mid_white)) return 0;
}
}
}
cout << "zbirka dozbirkoval" << endl;
}Existujú aj rôzne iné prístupy, ktoré sú založené na fixovaní nejakých iných psov, napríklad pravého dolného a ľavého horného. Tiež však v zásade ignorujú vopred zlé alebo už vyskúšané možnosti.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.