Krótki wstęp do algorytmów geometrycznych

09.12.2009 - Dominik Rusak
Trudność

 

 


Robot


Wyprodukowano robota, którego zadaniem jest automatyczne sprzątanie trasy, po której się porusza. Robot jest zasilany specjalną baterią, która ma ustaloną pojemność jednostek energii. Jest on tak skonstruowany, że skręcanie w prawo kosztuje go jedną jednostkę energii, zaś skręcanie w lewo odbywa się bez kosztów energetycznych. Ponadto, jeżeli przechodząc z jednego fragmentu trasy na kolejny, nie musi w ogóle skręcać (lub musi zawrócić), może się rozpędzić i załadować w ten sposób dodatkową jednostkę energii. Ponadto, gdy dwa kolejne odcinki na trasie pokrywają się, może odpocząć i również załadować dodatkową jednostkę energii. Dla trasy robota, podanej jako ciąg punktów <$ p_0,p_1,...,p_{n-1} $>, składajacej się z odcinków $ (p_0,p_1), (p_1,p_2),...,(p_{n-2},p_{n-1}) $ program ma za zadanie wypisać, czy z ustaloną ilością jednostek energii robot jest w stanie przebyć tę trasę.

Wejście:

W pierwszej linii znajduje się $ N $- liczba testów do rozpatrzenia.  W drugiej $ J $ - liczba jednostek energii, z którą robot zaczyna podróż. W kolejnych liniach znajdują się opisy testów, składające się z pojedynczej linii zawierającej liczbę $ n $, będącą liczbą punktów na trasie robota, i z $ n $ linii zawierających liczby $ x $ i $ y $, będące współrzędnymi kolejnych punktów. Zakres liczb: $ 0 \leq N \leq 10000 $, $ 0 \leq J \leq 100000 $, $ 0 \leq n \leq 100000 $,

$ -10^6 \leq x,y \leq 10^6 $.

Wyjście:

Dla każdego z testów należy w osobnej linii wypisać TAK, jeżeli robot da radę pokonać daną trasę z podaną liczbą jednostek energii, zaś NIE w przeciwnym przypadku.

Przykład:

Wejście:

4
3
5
2 2
3 6
-7 -2
-7 -2
6 -6
4
0 2
-2 -6
-4 0
-3 -6
10
7 2
-5 -5
-2 0
5 2
-5 -2
-2 -1
-7 0
-2 2
6 3
1 0
9
4 -4
6 -1
0 0
4 -7
0 6
5 3
-3 -6
0 -7
1 7

Wyjście:

TAK
TAK
NIE
TAK

 


Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Odcinki

Dla podanych par odcinków, należy odpowiedzieć, czy odcinki w obrębie danej pary przecinają się.

Wejście:

W pierwszej linii podane jest liczba testów - $ N $. W każdej z kolejnych $ N $ linii podane są współrzędne czterech punktów $ p_0 $, $ p_1 $, $ p_2 $, $ p_3 $: $ x_0 $, $ y_0 $, $ x_1 $, $ y_1 $, $ x_2 $, $ y_2 $, $ x_3 $, $ y_3 $. Zakres danych: $ 0 \leq N \leq 100000 $, $  -1000000 \leq x_i,y_i \leq 1000000 $, $ i = 0,1,2,3 $.

Wyjście:

Dla każdego z testów należy w osobnej linii wypisać TAK, gdy odcinki $ (p_0,p_1) $ i $ (p_2,p_3) $ przecinają się, zaś NIE w przeciwnym przypadku.

Przykład:

Wejście:

5
-9 3 -8 0 0 -1 2 4
4 0 -4 -2 5 0 8 -8
2 6 0 -9 2 -1 -6 2
-1 5 -3 -7 5 -3 1 -9
-1 0 1 -7 -5 1 6 0

Wyjście:

NIE
NIE
TAK
NIE
NIE
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.615385
Twoja ocena: Brak Ocena: 4.6 (13 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com