27235번 - 줄넘기

우경이는 $N$개의 밧줄을 가지고 줄넘기를 한다. 각각의 밧줄은 평면 위의 직선으로 나타낼 수 있으며, 일정한 속도로 평행이동하고 있다. 어떤 두 밧줄도 서로 평행하거나 일치하지 않는다. 우경이는 평면상의 밧줄이 지나지 않는 위치 $S$에서 줄넘기를 시작하며, 줄넘기를 하는 동안 원하는 경로와 속도로 자유롭게 이동할 수 있다. 이동 도중에 밧줄을 만날 때마다 밧줄을 한 번 넘은 것으로 센다. 한 번에 두 개 이상의 밧줄을 넘을 수는 없다.

우경이는 일정한 시간이 지나면 줄넘기를 멈출 것이다. 우경이는 줄넘기를 멈추기 전까지 밧줄을 넘는 횟수가 최소가 되도록 이동하고자 한다. 줄넘기를 멈췄을 때 우경이의 위치는 밧줄이 지나지 않는 곳이어야 하며, 시작한 위치와 달라도 된다. 우경이가 밧줄을 넘어야 하는 횟수는 최소 몇 번인지 구하라.

첫 번째 줄에 밧줄의 수 $N$이 주어진다.

두 번째 줄에 두 정수 $X,Y$가 주어진다. 우경이의 시작 위치 좌표가 $S=(X,Y)$임을 나타낸다.

세 번째 줄부터 $N$개의 줄에 밧줄의 정보를 나타내는 여섯 개의 정수 $x_1$, $y_1$, $x_2$, $y_2$, $a$, $b$가 주어진다. 우경이가 줄넘기를 시작했을 때 밧줄이 $(x_1,y_1)$과 $(x_2,y_2)$를 잇는 직선 형태이고, 우경이가 줄넘기를 멈출 때까지 밧줄이 $(a,b)$만큼 평행이동하게 됨을 의미한다.

우경이가 줄넘기를 멈추기 전까지 밧줄을 넘어야 하는 횟수의 최솟값을 출력한다.

• $1\leq N\leq 2\, 000$
• $|X|,|Y|,|x_1|,|y_1|,|x_2|,|y_2|,|a|,|b|\leq 1\, 000$
• $(x_1,y_1)\neq(x_2,y_2)$
• 우경이가 줄넘기를 시작했을 때, $S$는 평면상에서 밧줄 위에 있지 않다.
• 어떤 두 밧줄도 서로 평행하거나 일치하지 않는다.