문제
최근 홍윤시는 홍윤 공원의 야경을 빛나게 하기 위해 N개의 가로등을 설치했다.
이 가로등은 장애물없는 평면 구조의 석표 공원 위의 한 점으로 표현된다.
모든 가로등은 같은 방향을 바라보고 특정한 각도(예각) 범위의 영역을 비춘다.
빛은 무한히 멀리 퍼지며 다른 가로등에 막히지 않는다.
가로등은 1번부터 N번까지 각각 번호가 붙어 있다.
기본적으로 i번 가로등은 해가 지고 i초 후면 자동으로 켜진다.
또, 각 가로등은 고유한 센서 값 Ai가 존재해 Ai 이상의 빛을 받아도 켜진다.
즉, 아직 i초가 지나지 않았어도 자신을 비추는 가로등이 Ai개 이상이 되면 먼저 켜진다는 의미이다.
이때, 조명들이 켜지고 빛이 퍼지는데 걸리는 시간은 무시할 수 있을 정도로 짧다고 하자.
홍윤시의 성실한 공무원인 준혁이는 N개의 가로등이 각각 해가 지고 정확히 몇 초 뒤에 켜지게 되는지 조사해야 한다.
준혁이를 도와 가로등을 조사해보자!
입력
첫 줄에 N이 주어진다.
둘째 줄에 X1, Y1, X2, Y2가 주어진다.
이는 (x,y)에 있는 가로등이 (x+X1, y+Y1)와 (x+X2, y+Y2)방향 사이의 예각 범위를 비춘다는 의미이다.
그 다음 줄부터 i번째 줄에는 i번 가로등의 좌표 xi, yi가 주어진다.
마지막 줄에는 한 줄에 1번부터 차례대로 Ai가 주어진다.
<제한>
1 <= N <= 200000
-10^9 <= xi, yi, X1, Y1, X2, Y2 <= 10^9
1 <= Ai <= N
(Xi, Yi) != (0, 0)
출력
한 줄에 1번부터 N번까지 차례대로 각 가로등이 켜지는 시간을 출력하라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 30점 | |
| #2 | 70점 | 추가적인 제약 조건이 없다. |
예제
5
3 1 1 3
2 1
1 4
3 4
5 6
5 2
1 2 1 3 2
1 2 1 2 5
로그인해야 코드를 작성할 수 있어요.