Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
III Olimpiada Informatyczna 1995/96

Zadanie: ZAM
Autor: Krzysztof Diks
Zamek

Zawody I stopnia  
Plik źródłowy: ZAM.??? (np. pas, c, cpp)
Plik wykonywalny: ZAM.exe
Plik wejściowy: ZAM.in
Plik wyjściowy: ZAM.out

 

Poszukiwacze skarbów zdobyli mapę zamku, w którego podziemiach znajduje się olbrzymi skarb. Mapa jest naniesiona na siatkę kwadratową, której węzły mają współrzędne całkowite. Lewy dolny róg (węzeł) siatki ma współrzędne (0,0), a przeciwległy, prawy górny róg - współrzędne (10000, 10000). Na mapie zamek ma kształt wielokąta, którego boki leżą na liniach siatki. Kolejne dwa boki wielokąta są zawsze prostopadłe. Brzeg tego wielokąta jest łamaną zamkniętą zwykłą, tzn. każdy jej wierzchołek należy do dokładnie dwóch odcinków łamanej, a każdy inny punkt - do jednego. Odcinki linii tworzących siatkę zawarte w wielokącie, w tym także każdy bok wielokąta, przedstawiają odcinki podziemnych korytarzy zamku. W jednym z węzłów (tzn. na przecięciu linii siatki), należącym do wielokąta zaznaczony jest punkt wejścia do podziemi, a w innym węźle również należącym do wielokąta - punkt, w którym ukryty jest skarb.

Chcemy obliczyć długość najkrótszej drogi podziemnymi korytarzami zamku od punktu wejścia do podziemi do punktu, w którym ukryty jest skarb. Przyjmujemy, że jednostką długości jest długość boku pojedynczej kratki na siatce.

Zadanie

Napisz program, który:
  • wczytuje z pliku tekstowego ZAM.IN następujące dane o zamku:
    • liczbę wierzchołków n wielokąta przedstawiającego zamek, 4 <= n <= 5000,
    • współrzędne wierzchołków w kolejności ich występowania przy obchodzeniu wielokąta,
    • współrzędne punktu wejścia do podziemi i punktu, w którym ukryty jest skarb;
  • znajduje długość najkrótszej drogi podziemnymi korytarzami zamku (po liniach siatki), od punktu wejścia do podziemi do punktu, w którym znajduje się skarb;
  • zapisuje wynik w pliku tekstowym ZAM.OUT.

Wejście

W pierwszym wierszu pliku tekstowego ZAM.IN jest zapisana jedna liczba całkowita n z zakresu [4..5000] - jest to liczba wierzchołków wielokąta przedstawiającego zamek.

W każdym z kolejnych n wierszy są zapisane dwie liczby całkowite z zakresu [0..10000] oddzielone pojedynczym odstępem - są to współrzędne kolejnego wierzchołka wielokąta.

Następnie, w przedostatnim wierszu pliku są zapisane w takim samym formacie współrzędne punktu wejścia do podziemi, a w ostatnim wierszu współrzędne punktu położenia skarbu.

Wyjście

W pierwszym i jedynym wierszu pliku tekstowego ZAM.OUT należy zapisać jedną liczbę całkowitą - długość najkrótszej drogi od punktu wejścia do podziemi do punktu w którym ukryty jest skarb.

Przykład

Opisem zamku przedstawionego na rysunku jest następujący plik tekstowy ZAM.IN
10
9 6
9 2
12 2
12 9
2 9
2 1
8 1
8 3
4 3
4 6
11 5
3 1

Poprawnym rozwiązaniem jest w tym przypadku następujący plik ZAM.OUT:

14

Twój program powinien szukać pliku ZAM.IN w katalogu bieżącym i tworzyć plik ZAM.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę ZAM.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku ZAM.EXE.




Wersja do druku