시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB (추가 메모리 없음)50242145.652%

문제

좌표 평면 위에 $N$개의 구슬 발사기가 있다. 발사기에서 발사된 구슬은 발사기를 만나기 전까지 무한히 이동한다. 구슬이 이동 중에 발사기를 만나면 발사기가 바라보는 방향으로 다시 발사되며, 발사기를 방문하지 않고 지나칠 수는 없다. 구슬 발사기는 북, 북동, 동, 남동, 남, 남서, 서, 북서 이렇게 $8$가지 방향을 바라볼 수 있다. 또한 발사기의 방향을 시계방향으로 원하는 만큼 회전시킬 수 있는데, 발사기 $i$를 $45$도 회전하기 위해 필요한 비용은 $c_{i}$이다. 발사기는 최대 한 번 구슬을 발사할 수 있다. 따라서 한 번 사용된 발사기에 구슬이 방문한다면 더 이상 구슬이 이동하지 않고 그 발사기에 멈춘다. 

발사기의 방향을 적절히 회전하여, 구슬을 발사기 $s$에서 발사기 $e$까지 최소 비용으로 도달하게 하려고 한다. 이 때 최소 비용과 어느 발사기를 거쳐서 이동했는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 정수 $N$, $s$, $e$ 이 주어진다. ($2 \leq N \leq 100\,000, 1 \leq s, e \leq N, s \ne e$)

다음 $N$개의 줄에 걸쳐 발사기 $i$의 정보 $x_{i}$, $y_{i}$, $c_{i}$, $d_{i}$가 공백으로 분리되어 주어진다.

  • $x_{i}$와 $y_{i}$는 각각 발사기 $i$의 $x$좌표와 $y$좌표이다. ($1 \leq x_i, y_i \leq 10^{9}$)
  • $c_{i}$는 발사기 $i$를 회전하는데 필요한 비용이다. ($0 \leq c_i \leq 200\,000$)
  • $d_{i}$는 발사기 $i$가 초기에 바라보고 있는 방향이다. 알파벳 대문자 N, NE, E, SE, S, SW, W, NW중 하나이며 각각 북, 북동, 동, 남동, 남, 남서, 서, 북서 방향을 의미한다.

서로 다른 두 발사기가 같은 좌표에 존재하지 않으며, 모든 $i$에 대하여 $x_i$, $y_i$, $c_i$는 정수이다.

출력

첫 번째 줄에 최소 비용을 출력한다.

두 번째 줄에 발사기 $s$와 발사기 $e$를 포함하여, 이동한 발사기의 번호를 출력한다. 만약 최소 비용으로 이동할 수 있는 경로가 여러 가지라면 아무거나 출력한다.

만약 발사기 $e$까지 도달하는 것이 불가능하면, 첫 번째 줄에 $-1$을 출력한 뒤 종료한다.

예제 입력 1

4 1 4
1 5 1 E
5 5 2 SE
5 1 4 W
1 1 3 N

예제 출력 1

1
1 3 4

예제 입력 1을 좌표 평면에 표기하면 아래 그림과 같다. 각 점은 구슬 발사기를 의미하며, 화살표 방향은 발사기가 초기에 바라보고 있는 방향이다.

이 상황에서 최선의 방법은 아래 그림과 같이 1번 발사기를 한 번 회전하는 것이다.

예제 입력 2

4 1 4
1 4 4 S
4 5 2 SW
5 2 1 N
2 1 3 W

예제 출력 2

-1

예제 입력 2를 좌표 평면에 표기하면 아래 그림과 같다. 이 상황에서 구슬 발사기를 어떻게 회전하더라도 1번 발사기에서 4번 발사기로 도달할 수 없다.

노트

동쪽이 $x$좌표가 증가하는 방향, 북쪽이 $y$좌표가 증가하는 방향이다.

출처

University > 홍익대학교 > 2021 홍익대학교 프로그래밍 경진대회 J번