|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||0||0||0||0.000%|
On one fine day, Mr. Panda and Rar the Cat decide to go rock climbing. The rock climbing wall has N rocks. The i-th rock is located at height Yi from the bottom of the wall and Xi units right from the centre of the wall. If Xi is negative then it is to the left of the centre. The positions of all rocks are different.
To test Mr. Panda’s rock climbing skills, Rar the Cat decided to issue a challenge to him. The challenge is as follows:
Refer to the sample input and output for more details.
Of course, Mr. Panda knows that there are many pairs of rocks such that the challenge cannot be completed. He wants to find the minimum K such that no matter what set of rocks Rar the Cat chooses, he can always complete the challenge. He needs your help to find this value.
Your program must read from standard input. The first line of input contains one integer N. The next N lines contain 3 integers each. The (i + 1)-th line represents Xi, Yi, Si for the i-th rock.
You program must output one line with a single integer to the standard output, which is the minimum number of rocks so that Mr. Panda can always complete the challenge. If Mr. Panda can never complete the challenge, output −1.
5 0 3 2 -1 5 1 4 4 3 -1 1 2 2 2 1
When K = 2, there exists some subset of rocks so that Mr. Panda cannot complete the challenge. For example, if Rar the Cat chooses the rocks on (−1, 1) and (2, 2) to form the set R, Mr. Panda cannot complete the challenge. Mr. Panda cannot move from the rock on (2, 2) to the rock on (−1, 1) since he can only climb upward. Mr. Panda cannot move directly from the rock on (−1, 1) to the rock on (2, 2) since max(| − 1 − 2|, |1 − 2|) = 3 > max(2, 1) = 2.
Another choice is to move indirectly from (−1, 1) to (2, 2). Mr. Panda can climb from the rock on (−1, 1) to the rock on (0, 3) since max(| − 1 − 0|, |1 − 3|) = 2 ≤ max(2, 1) = 2. However, he cannot move from the rock on (0, 3) to the rock on (2, 2) since he must climb upwards.
Moreover, it can be verified that for every set of 3 rocks, there is always a way to pick a pair of rocks so that the Mr. Panda can complete the challenge. For example, if Rar the Cat picks the rocks on (−1, 5),(4, 4),(−1, 1) to form set R, Mr. Panda can complete the challenge by picking the rocks on (−1, 5) and (−1, 1). To complete the challenge, he climbs from the rock (−1, 1) to the rock on (0, 3) then to the rock on (−1, 5). The intermediate rocks do not need to be from R.
3 0 1 2000000 -1 2 2000000 1 2 2000000
If Rar the Cat selects the 2 rocks on height 2 (i.e. the 2nd and the 3rd rocks), Mr. Panda cannot complete the challenge since he must always climb upwards. So Mr. Panda can only guarantee that he can complete the challenge if Rar the Cat chooses all the rocks.
2 0 1 1 0 5 1
Even if Rar the cat selects all the rocks Mr. Panda since there is no way to get from one rock to another. Thus, Mr. Panda can never complete the challenge.