CSCB325

Задачи 2022

Задача 9. Parallel2022
Зададени са N на брой отсечки с координатите на техните крайни точки, където N ≤ 1000. Координатите на точките са цели числа в интервала [−500,500]. Задачата е да се намери броят на всички множества от успоредни, съвпадащи или лежащи на една права отсечки.

Вход:
Входът има следния формат: на първия ред има цяло число, оказващо броя на отсечките N. На останалите N на брой редове са дадени координатите на крайните точки на всяка една отсечка. На всеки ред координатите са подредени както следва: x-координата, y-координата на първата точка, x-координата, y-координата на последната точка. На входа са зададени много примери.

Изход:

За всеки пример изходът е цяло число, оказващо броя на търсените класове, записано на отделен ред.

Пример:
5
0 3 4 3
1 -3 1 -1
14 0 13 5
1 1 3 2
6 0 5 5

Решение на примера:
4
Обяснение на примера: Третият и петият вектори са успоредни, други успоредни вектори няма. Затова класовете са четири - 3 от тях се състоят от множества по един елемент и един - от множество с два елемента.

Задача 10. Convex2022
Дадено е множество от точки в равнината. Да се намери изпъкналата обвивка на множеството.

Вход:
За всеки пример от стандартния вход се чете цяло число n - броя на точките в множеството. Следват n реда с координетите на точките, цели числа в интервала [-1000, 1000]. Входът съдържа много примери.

Ограничения:
n < 1000

Изход:
За всеки пример на стандартния изход се отпечатва по едно число на отделен ред - броя на върховете на многоъгълника - изпъкнала обвивка на множеството.

Пример:
5
0 0
-1 -1
1 1
1 -1
-1 1

Решение на примера:
4