405706: GYM102051 G Nate and Game

Nate found a game under his bed! He was not familiar with it, so he decided to load it in his game console. When the game finally started, Nate was greeted with the title screen, "AttAck on Eoten!" Nate was excited because this was his favorite cartoon! He was excited for an action-packed game with a compelling story. Strangely though, it seems like the models were all off. The giants, which were supposedly humanoid, now look like triangles!

Although Nate was slightly disappointed, he still pushed through with the game. After playing for $$$420$$$ minutes, he forgot they were giants so he just simply called them as triangles.

The mechanics of the game is fairly simple. Nate was stationed in a castle on the leftmost of the screen and he had to shoot with his gun to destroy triangles. The game is fairly old, so he could only shoot in a horizontal trajectory. He also noticed that hitting even just the border of a triangle would destroy it. After playing for $$$6969$$$ minutes, he noticed that the game was lazily coded: some triangles were overlapping.

After playing for $$$42069$$$ minutes, he got a sniper rifle with exactly $$$1$$$ piercing shot. A piercing shot can shoot through any number of triangles as long as they all intersect the line of fire. Nate was pretty tired already, and he just wants to shoot as many triangles in one shot. Since there were a lot of triangles on the screen, he could not determine how many he could shoot at once. Can you help him find the maximum number of triangles he can shoot in one shot?

The first line of input contains a single integer $$$n$$$, the number of triangles.

The next $$$n$$$ lines of input each contain six space-separated integers, $$$x_0,y_0,x_1,y_1,x_2,y_2$$$, respectively, where $$$(x_0,y_0),(x_1,y_1),(x_2,y_2)$$$ are the three vertices of a triangle. It is guaranteed that the triangles are non-degenerate, i.e. the three points of each triangle are not collinear.

Constraints

$$$1 \leq n \leq 142069$$$

$$$-1000000 \leq x_0,y_0,x_1,y_1,x_2,y_2 \leq 1000000$$$

Output a single integer, the maximum number of triangles Nate can hit.

1
0 6 -5 1 6 -8

1

2
0 4 -10 7 6 9
-2 -2 -6 -9 3 -7

1

5
-3 5 -8 2 -5 7
1 -5 3 -7 5 0
1 4 2 6 5 5
-2 -3 -3 3 -5 -2
1 -1 2 1 -1 2

3

For the third test case, the input would look like this. Nate can hit $$$3$$$ triangles by shooting his rifle as in the red line in the figure. There are other ways for Nate to hit $$$3$$$ triangles, but Nate cannot hit more than $$$3$$$ triangles in one shot.