1. 출제자가 의도한 풀이는 이분매칭

2. 이 문제를 보고 감이 안와서 질문들을 보고 해결

3. min, max 범위를 계속 구하고

4. 마지막에 min > max + 앱실론 으로 확인

5. 실수 연산에는 앱실론을 앞으로 거의 계속 사용하자.

문제

심술쟁이 해커 임준오(동탄 주민)는 오늘도 점심시간을 기다리고 있다. 준오와 친구들은 매일 복도 어딘가의 한 지점에 모여서 함께 밥을 먹으러 간다. 선린의 복도는 직선형으로 되어있고, 준오와 친구들은 이 복도 어딘가에 위치한 교실에서 종이 치기만을 기다리고 있다.

‘띵~ 디딩~ 띵디딩디딩~’

종이 울렸다! 준오와 친구들은 최대한 빨리 한 지점에서 만나야한다. 그렇지 않으면 홍수처럼 쏟아지는 학생들에 휩쓸려 제각각 급식실로 떠내려갈지도 모른다.

준오를 포함한 친구들의 교실 위치 xi와 각 학생들의 달리기 속도 vi, 그리고 홍수가 밀려오기까지 남은 시간 T가 주어진다. 과연 준오와 친구들은 함께 밥을 먹으러 갈 수 있을까?

교실은 1차원 직선 위 어딘가에 위치해있다. 학생들의 달리기 속도는 항상 일정하며, 모든 학생들이 종이 울림과 동시에 뛰어나온다. 홍수가 터지는 시점과 친구들이 만나는 시점이 일치한다면 홍수에 떠내려가기 전에 만날 수 있는 것으로 간주한다.

입력

첫째 줄에는 준오를 포함한 친구들의 수 N과 홍수까지 남은 시간 T가 주어진다. (1 ≤ N ≤ 50,000, 1 ≤ T(초) ≤ 1,000,000,000) 남은 시간 T는 소숫점 넷째자리의 실수로 주어진다.

둘째 줄에는 N명 학생들의 위치 x1, x2, ..., xn(1 ≤ xi ≤ 1,000,000,000)가 주어진다. (자연수, 미터 단위)

셋째 줄에는 N명 학생들의 속도 v1, v2, ..., vn(1 ≤ vi ≤ 1,000,000,000)가 주어진다. (자연수, 초당 미터)

출력

준오와 친구들이 모두 만날 수 있으면 1을, 그렇지 않으면 0을 출력한다.


+ Recent posts