LCC/Moose '20 Contest 5 S4 - Ninjaclasher's Mobs

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Ninjaclasher is playing minecraft! He has N mobs in his farm, each with a type from 1 to M. There is at least one mob of each type. He wants to become more organized, so he wants to build a pen for one of his mobs. Specifically, he wants his pen to enclose all the mobs of some type C, yet not enclose any mobs not of type C. He also wants to be able to walk in a straight line from his base to his mine without having to go through more than 2 fence gates. However, you do not know where his base or his mine are (that is a secret), so you want to build the enclosure such that no matter where his base and his mine are, he can walk from his base to his mine without crossing the enclosure boundary more than twice. Can you help him determine if this is possible? As the farm is gigantic, you can assume the plane is continuous (i.e. there is an arbitrarily large number of blocks in [x,x+\epsilon) \times [y,y+\epsilon) for \epsilon>0).

Input Specification

The first line will contain two integers N\ (1 \leq N \leq 2\cdot 10^3), M\ (1 \leq M \leq N), the number of mobs, and the number of different types of mobs.

The next N lines will contain 3 integers x_i,y_i\ (-10^9 \leq x_i,y_i \leq 10^9), c_i\ (1 \leq c_i \leq M), the position and type of each mob.

Output Specification

Print YES if some mob can be enclosed, or NO otherwise.


Subtask 1 (50%)

N \leq 500

Subtask 2 (50%)

No further constraints.

Sample Input

6 2
0 0 1
2 2 1
2 0 1
1 1 2
2 3 2
3 1 2

Sample Output



There are no comments at the moment.