문제
레이 트레이싱은 실제 그래픽 프로그래밍에 사용되는 기법이다. 이번 기회에 배워보도록 하자.
X와 Y로 이루어진 격자를 생각해 보도록 하자. (0,0)에 서 있는 당신이 (x0,y0)에 레이저 빔을 쏘면,
그 빛은 당신이 발사한 방향으로 직진할 것이다. 직진한 빛은 어떤 물체에 맞거나, 끝없이 직진한다.
이 격자에는 n개의 물체들이 있다. 1번부터 n번까지의 물체들은 모두 선분의 형태를 띠고 있다.
그래픽 프로그래밍 신입생으로써의 당신의 첫걸음은, 가장 먼저 레이저 빔을 맞는 물체를 찾아내는 것이다.
이를 찾아내는 프로그램을 작성하라.
입력
표준 입력으로 다음이 주어진다.
첫 줄에 x0과 y0이 공백을 사이에 두고 주어진다.
둘째 줄에 물체(선분)의 수인 n이 주어진다.
다음 n줄에 걸쳐 물체(선분)의 양 끝 좌표인 x1, y1, x2, y2가 주어진다. 이는 이 선분이 (x1, y1)부터 (x2, y2)까지의 직선임을 의미한다.
제약 조건
모든 부분문제에 있어서 0≤x≤1,000 , 0≤y≤1,000 을 만족한다.
모든 부분문제에 있어서 1≤n≤500 을 만족한다. x0이나 y0중 하나는 0이 아님을 보장한다.
출력
표준 출력으로 가장 먼저 레이저 빔을 맞는 물체의 번호를 출력한다.
가장 먼저 레이저 빔을 맞는 물체의 번호가 2개 이상인 경우 물체의 번호가 작은 것을 출력한다.
만약 아무 물체도 레이저 빔을 맞지 않는다면, -1을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 14점 | n = 1 |
| #2 | 21점 | 모든 물체들의 기울기는 서로 같다. |
| #3 | 7점 | x0이나 y0중 한 값은 0이다. |
| #4 | 58점 | 주어진 조건 외 아무런 제약조건이 없다. |
예제 #1
1 1
2
1 2 3 1
1 3 4 2
1
예제 #2
0 1
3
1 2 2 1
1 1 2 2
2 3 3 2
-1
로그인해야 코드를 작성할 수 있어요.