Задача learning. У машинному навчанні часто виникає завдання лінійної класифікації об'єктів, коли класи об'єктів поділяються між собою лінійною поверхнею. Наприклад, у нас є інформація про кількість днів з моменту реєстрації облікового запису в соціальній мережі та кількість надісланих повідомлень за останній день, а також інформація про те, чи є цей обліковий запис спам-ботом. Вік облікового запису ми можемо взяти за X координату точки, а кількість повідомлень за Y координату. Завдання класифікац
ії полягає в тому, щоб провести якусь пряму так, щоб об'єкти одного тину знаходилися по одну сторону цієї прямої, а об'єкти іншого тину та іншу.
За наявності такої прямої ми зможемо прогнозувати тип навіть незнайомого об'єкта але відомому віку облікового запису та кількості відправлених повідомлень залежно від того, з якого боку від прямої виявився об'єкт. Звичайно, у реальних даних можуть бути помилки вимірів або незвичайні об'єкти і провести таку пряму не всіх так можливо, тому що, наприклад, об'єкт першого тину може випадково потрапити в скупчення об'єктів другого типу і відокремити його прямо неможливо.
Вам необхідно за інформацією про параметри та тип об'єктів визначити, чи існує пряма, яка однозначно поділяє класи об'єктів. Пряма не повинна проходити ні через один об'єкт.
Технічні умови. Програма Learning читає з пристрою стандартного введення кілька тестових блоків. У першому рядку задано число Т - кількість тестових блоків (1 ≤ Т ≤ 100). Кожен тестовий блок складається з числа N - кількість описаних об'єктів (1 ≤ N ≤ 2000). У наступних N рядках міститься опис об'єктів, що складаються з трьох цілих чисел X, У, Туре (0 < X, У < 107, 0 ≤ Туpe ≤ 1). Програма виводить на пристрій стандартного виведення для кожного тестового блоку YES, якщо поділ можливий і NO, якщо ні, для кожного блоку в окремій стрічці.
Приклад
|
Введення |
Виведення |
|||
|
2 |
|
|
|
YES |
|
6 |
|
|
|
NO |
|
1 |
1 |
1 |
|
|
|
1 |
2 |
1 |
|
|
|
1 |
3 |
0 |
|
|
|
2 |
1 |
1 |
|
|
|
2 |
2 |
0 |
|
|
|
3 |
1 |
0 |
|
|
|
6 |
|
|
|
|
|
1 |
3 |
0 |
|
|
|
2 |
2 |
0 |
|
|
|
1 |
2 |
1 |
|
|
|
3 |
1 |
1 |
|
|
|
2 |
1 |
1 |
|
|
|
1 |
1 |
0 |
|
|