Наблюдение на езеро (Алгоритмична)


Преди няколко години властите установили, че пъстървата в Охридското езеро е намаляла драстично. Решили да забранят риболова за десетгодишен период. Но все още има доста бракониери. За да ги контролират, решили да монтират 360 градусова камера на някаква позиция в езерото, така че да може да се наблюдава цялото езеро. Езерото е многоъгълник, зададен чрез координатите на върховете си по посока на часовниковата стрелка. Вашата задача е да откриете дали има позиция в езерото, така че цялото езеро да се вижда от тази точка.

Вход
Първият ред съдържа числото n ≤ 3 – брой на тестовите примери. Всеки тестов пример започва с число k, 4 ≤ k ≤ 100, броят на върховете на езерото. На следващите k реда има по две цели числа xi и yi, и двете между –30 000 и 30 000, координатите на i-тия връх на езерото. Бреговата линия на езерото представлява затворена начупена линия без самопресичания.

Изход
За всеки тестов пример на отделен ред трябва да се изведе YES, ако има позиция за камерата и NO, ако не е възможно да се намери подходящо място за камерата.
Оценяването ще става за две множества от входни данни.
Първото множество от тестови данни (4 от 10) ще съдържа само тестове, за които страните на езерото са хоризонтални или вертикални.
Второто множество (6 от 10) ще бъде без ограничения за страните на многоъгълника.

Пример

Вход:
2
4
0 0
0 1
1 1
1 0
6
0 0
1 2
1 1
2 1
2 2
3 0

Изход:
Yes
No

  1. Няма коментари.
(will not be published)