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