Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_04_01 - Dostawca PRK |
Ostatniego tygodnia tajemnicza osoba PRK, pseudonim Prawie Rudy Kocur, kupił sobie prawo
jazdy i szef mianował go naczelnym bułkowym. Jest to bardzo odpowiedzialna praca,
ponieważ musi on rozwozić pyszne wyroby do swoich klientów, którzy czekają na niego w
odpowiednich miejscach. Prawo jazdy nie kosztowało go mało, więc postanowił sobie
zaoszczędzić trochę pieniążków na benzynie. Jego zadanie na dziś jest dość wymagające.
Musi się on opiekować N lokalami. Opieka polega na tym, że jeżeli lokal A pokłóci się z
lokalem B to PRK musi przywieźć trochę pysznych wyrobów z lokalu B do lokalu A. Po takiej
dostawie owe dwa lokale żyją już w zgodzie i nigdy się nie kłócą. PRK wpadł na świetny
pomysł, aby zatankować "na styk", czyli tak, aby móc zrealizować wszystkie ewentualne
dostawy. PRK przekazał tobie mapę ze współrzędnymi obsługiwanych lokali, na której w rogu
widnieje napis:"Poruszać się pionowo i poziomo do osi współrzędnych". Twoim zadaniem jest
wyliczenie sumy odległości wszystkich ewentualnych dostaw, on już sam zajmie się
tankowaniem swojego pojazdu.
Input
W pierwszym wierszu liczba N (1< N <= 10^5) oznaczająca liczbę obsługiwanych lokali.
W następnych N wierszach po dwie liczby x_i oraz y_i ( |x_i|,|y_i| <= 10^9 ) oznaczające współrzędne i-tego lokalu.
Output
Liczba oznaczająca sumę dystansów.
Example
Input:
3
0 0
1 1
2 2
Output:
8
Dodane przez: | Krzysztof Lewko |
Data dodania: | 2013-01-27 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 GOSU |
Pochodzenie: | AlgoLiga 4 |