Editorial for Vorpspejs


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Analiza

Primetimo da koordinate možemo da posmatramo nezavisno. Najlakši način da rešimo zadatak je analizom slučajeva. Za obe koordinate razmatramo dva slučaja, da li smo prešli preko ivice ili ne. Posmatrajmo x koordinatu početnog i krajnjeg polja. Ukoliko nismo prešli ivicu od polja A_{x} do polja B_{x}, rastojanje je |A_{x}-B_{x}|. Ukoliko jesmo i dužina vorp-spejsa je D_{x}, rastojanje je D_{x}-|A_{x}-B_{x}|. Dakle, minimalan broj koraka da bi smo se našli na x koordinati na kojoj je krajnje polje je \min(|A_{x}-B_{x}|,D_{x}-|A_{x}-B_{x}|). Sličan rezultat dobijamo za y koordinatu, \min(|A_{y}-B_{y}|,D_{y}-|A_{y}-B_{y}|). Ukupan broj koraka je \min(|A_{x}-B_{x}|,D_{x}-|A_{x}-B_{x}|) + \min(|A_{y}-B_{y}|,D_{y}-|A_{y}-B_{y}|).


Comments

There are no comments at the moment.