Задачи от 2.11.2001

Задача 1.  Път в граф
Даден е насочен граф и два негови върха. Да се намери път между тях.

Вход:
Граф, зададен с двойки числа в скоби - дъгите на графа, празен ред, две числа - върхове на графа.

Изход:
Редица от номера на върхове.

Примерен вход:
(1,2) (1,5) (2,1) (2,5) (3,2) (3,4) (4,3) (4,5) (5,1)

4 2

Примерен изход:
4 5 1 2


Задача 2. Коза в градината
Предисловие:
Една коза стои в центъра на градина с трева с форма на квадрат със страна а. Козата е вързана с въже с дължина L за метален кол. Тя е много гладна и може да изяде всичката трева, до която може да достигне. Приема се че отвъд квадрата няма трева.

Задача:
По зададените а и L да се намиери площта трева, която козата може да изяде.

Вход:
а и L разделени с един интервал, естествени числа ненадвишаващи 100.

Изход:
Площта, с 3 цифри след десетичната запетая.

Примерен вход:
10 6

Примерен изход:
95.091


Задача 3. Вътрешна точка
Даден е многоъгълник в равнината без самопресичане като крайна редица от координати на върховете му. Дадена е и точка в равнината. Да се определи дали точката е вътрешна за многоъгълника.

Вход:
На първия ред на входния файл е зададено естественото число N, N<=1000 - броя на върховете на многоъгълника. В следващите N +1 реда са зададени координатите на върховете му, като два съседни върха са зададени на два съседни реда. На последния ред са координатите на дадената точка. Координатите са числа с една цифра след десетичната точка.

Изход:
На първият и единствен ред на изходния файл да се запише 1 ако точката е вътрешна или 0 ако не е.

Примерен вход:
5
-1.0 0.0
1.0 0.0
1.0 2.0
0.0 1.0
-1.0 2.0
0.9 0.5

Примерен изход:
1


Задача 4. Лифт
В силно пресечена планинска местност ще се изгражда лифт. Началната и крайната точка са определени и е направен профил на терена над който ще върви линията. Резултатът е полигон в равнинна координатна система с начало, съвпадащо с началната станция. Точките на полигона, започвайки с началната и завършвайки в крайната, са избрани през 1 метър (по оста X) и са измерени надморските им височини. Предполага се, че между две съседни точки теренът върви по права линия. Задачата е да се направи програма, която да определи минимален брой от точките на полигона, в които да се поставят опорните стълбове на лифта. Стълбовете трябва да са поставени така, че линията да не докосва терена.

Вход:
На първия ред на входния файл е зададено естественото число N, N<=30000 - разстоянието в метри (по оста X) между началната и крайната станция. В следващите N +1 реда са зададени надморските височини на точките на полигона - числа с една цифра след десетичната точка.

Изход:
На първият и единствен ред на изходния файл да се запише намереният минимален брой.

Примерен вход:
6
8.0
5.0
10.0
10.0
10.0
6.0
9.0

Примерен изход:
4