Ladybugs race

Johnny has organized a ladybug race on his school desk.

Assume the desk is flat and that the coordinates of the points are described by their Cartesian coordinates (x, y). Each of the n ladybugs taking part in the race has been placed at some point along the starting-line, i.e. at the point with coordinates (xSi, 0) for the i-th ladybug, and was informed about its own individual end point (xFi, yFi) of the race, where 1 ≤ in. After the start of the race, all ladybugs always follow the shortest path directly to their target but not necessarily at a constant speed.

When the teacher found out about the planned race she strongly protested. She said that it was unacceptable that the routes followed by the ladybugs intersect, and that the poor insects could bump into each other.

Johnny was therefore instructed to change the idea of the race. It was already too late to change the racetracks so it was necessary to withdraw some of the ladybugs from the race.

Your task is to determine the maximum number of ladybugs which can remain in the competition, without having their trajectories intersect.


The first line gives an integer n which determines the initial number of ladybugs taking part in the race (1 ≤ n ≤ 200). Next n rows gives three integers xSi, xFi, yFi which are separated by a space. Those three numbers describe the start and end points of routes for each individual ladybug (-40000 ≤ xSi, xFi ≤ 40000, 0 ≤ yFi ≤ 40000).


Write the maximum number of ladybugs which can remain in the race so that no two racetracks of the remaining ladybugs intersect. The racetracks are straight-line segments, including their start and end points.


Test case 1

0 0 10
-10 0 10
10 0 10 


Test case 2

0 2 2
2 1 2
3 3 2
4 4 4
3 4 2
4 3 2


Please log in to submit your solution.