개구리 점프(frogjump) > 문제은행



알고리즘 백트랙킹1

3431 : 개구리 점프(frogjump)

제한시간: 1Sec    메모리제한: 1024mb
해결횟수: 53회    시도횟수: 297회   



통나무 N개가 가로 (수평) 방향으로 연못에 떠 있다. 

개구리는 한 통나무 A에서 다른 통나무 B로 정확히 수직 방향으로 점프할 수 있다. 

단, 점프할 때 다른 통나무 위를 (끝 점 포함) 지나면 안된다.

 

예를 들어 <그림 1>에서 1번 통나무에서 2번 통나무로 점선을 따라 개구리가 점프하는 것이 가능하다. 

1번 통나무에서 2번 통나무로 점프한 후 다시 3번 통나무로 점프하면 1번 통나무에서 3번 통나무로 이동하는 것이 가능하다.

(통나무 위에서 걸어서 움직이는 것은 언제든 가능하다.)​

 

a11be9d5e48052714177281e98df476b_1564623
 

 

통나무들의 위치를 입력받아 질문으로 주어진 통나무들의 쌍에 대해서 개구리가

한 통나무에서 다른 통나무로 한번 이상의 점프로 이동이 가능한지 판단하는 프로그램을 작성하라.​


표준 입력으로 다음 정보가 주어진다. 
첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 
다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 
주어진 통나무는 두 점 (x1, y)(x2, y)를 잇는 형태이다. 
(x1 < x2) 모든 좌표는 0 이상 109 이하이다. 
통나무들은 주어진 순서대로 1번부터 번호가 붙어 있다. 
서로 다른 두 통나무는 (끝점에서도) 만나지 않는다. 
다음 Q개의 줄에 서로 다른 두 통나무의 번호가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)


표준 출력으로 Q개의 줄을 출력한다. 각 줄에는 주어진 순서대로 질문에 대한 대답이 출력되어야 한다. 
질문에 주어진 두 통나무에 대해서 개구리가 한 통나무에서 다른 통나무로 
한번 이상의 점프로 이동이 가능한 경우 대답은 1, 그렇지 않은 경우 대답은 0이다.

[부분문제의 제약 조건]
* 부분문제 1: 전체 점수 100점 중 19점에 해당하며 모든 좌표는 0이상 1,000이하이고,
              1 ≤ N ≤ 100, 1 ≤ Q ≤ 100 이다.
* 부분문제 2: 전체 점수 100점 중 31점에 해당하며   1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100 이다.
* 부분문제 3: 전체 점수 100점 중 50점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다

[Copy]
4 2
1 5 2
3 7 4
7 9 1
10 13 4
1 3
1 4
[Copy]
1
0






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.