ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#8635

쉬운 버스 갈아타기 1s 32MB

問題

2차원 평면상에 m개의 수직선과 n개의 수평선으로 이루어진 격자 형태의 도로망이 있다. 

아래 그림은 7개의 수직선과 6개의 수평선으로 이루어진 도로망의 예이다.  

수직선과 수평선이 만나는 교차점들 중 가장 왼쪽 아래 점의 위치는 (1,1)이고, 가장 오른쪽 위 점의 좌표는 (m,n)이다. 

이 도로망을 운행하는 버스들이 k개 있고, 각 버스는 하나의 수평선 상의 두 교차점 사이 선분이나 하나의 수직선 상의 두 교차점 사이 선분을 왕복 운행한다. 

각 버스는 운행하는 선분 사이의 모든 교차점(선분의 양 끝 교차점 포함)에서 정차한다.

버스 회사의 규정 상 환승은 딱 한 번 가능하고, 버스의 노선 상 겹치는 위치가 있는 경우 가능하다.

두 버스의 번호 x와 y가 주어졌을 때, x버스에서 y버스로 갈아타는 것이 가능한지 출력하는 프로그램을 작성하시오. 

예를 들어,  8대의 버스가 다음과 같이 운행한다고 하자.

  • 1번 버스: (2, 1) - (2, 2)

  • 2번 버스: (1, 1) - (5, 1)

  • 3번 버스: (3, 2) - (6, 2)

  • 4번 버스: (5, 6) - (5, 1)

  • 5번 버스: (1, 5) - (7, 5)

  • 6번 버스: (7, 3) - (7, 6)

  • 7번 버스: (2, 1) - (2, 6)

  • 8번 버스: (3, 5) - (6, 5)

현재 타고 있는 버스 x=2번 버스이고 갈아타고 싶은 버스가 y=4번 버스라고 하자. 

2번 버스를 타고 교차점 (5, 1)에서 내려, 4번 버스를 타면 갈아타는 것이 가능하다.

x = 8 이고, y=5 인 경우 (5, 5)에서 갈아타면 되기에 이 또한 가능하다.

하지만, x = 3 이고, y = 6인 경우 서로 교차하는 위치가 없기에 갈아타는 것이 불가능하다.


入力

첫 번째 줄에 수직선의 수 m과 수평선의 수 n이 빈칸을 사이에 두고 주어진다.

두 번째 줄에 버스의 수 k가 주어진다. 

세 번째 줄부터 k줄에 걸쳐 각 줄에 버스의 운행구간을 나타내는 5개의 수 b, x_1, y_1, x_2, y_2가 빈칸을 사이에 두고 주어진다. 

여기서 b는 버스의 번호, (x_1,y_1)과 (x_2,y_2)는 이 버스가 운행하는 양쪽 끝 교차점의 좌표를 나타낸다. 

마지막 줄에 두 버스의 번호를 나타내는 두 개의 수 x, y가 빈칸을 사이에 두고 주어진다. 

[제약 조건]

  • 1 ≤ m,n ≤ 100,000

  • 1≤k≤5,000

  • 1≤b≤k

  • 1 \le x, y \le k

  • x \ne y


出力

첫 줄에 x번 버스에서 y번 버스로 갈아타는 것이 가능하면 Y를 출력하고, 불가능하면 N을 출력한다.


例題 #1

7 6
8
1 2 1 2 2
2 1 1 5 1
6 7 3 7 6
7 2 1 2 6
3 3 2 6 2
4 5 6 5 1
5 1 5 7 5
8 3 5 6 5
2 4
Y

例題 #2

7 6
8
1 2 1 2 2
2 1 1 5 1
6 7 3 7 6
7 2 1 2 6
3 3 2 6 2
4 5 6 5 1
5 1 5 7 5
8 3 5 6 5
8 5
Y

例題 #3

7 6
8
1 2 1 2 2
2 1 1 5 1
6 7 3 7 6
7 2 1 2 6
3 3 2 6 2
4 5 6 5 1
5 1 5 7 5
8 3 5 6 5
3 6
N

ログインしないとコードを書けません。