문제
시논은 유명한 저격수이다. 그녀는 시야가 넓고 판단력이 좋기로 유명했기에, 이번에 추가되는 전쟁 컨텐츠에서 정부군의 사령관 역할을 맡게 되었다.
전쟁에서 제일 중요한 것은 통신이다. 이를 위해, 시논은 플레이어들 간에 무전기 아이템을 통해 통신을 시키려고 한다.
무전기 아이템은 어떤 플레이어와 다른 플레이어 간에 프라이빗 채널을 열어 보이스챗을 가능하게 하는 아이템이다.
그런데, 모든 플레이어들 간에 무전기를 연결하는 것은 오히려 통신을 혼란스럽게 할 것이라고 생각했다.
(100 vs 100 게임을 하는데 100명의 보이스가 동시에 들린다고 생각해보라. 또한, 10000개의 무전기를 준비하는 것도 힘들다.)
따라서 시논은 무전기 아이템을 적당히 할당하여 전쟁을 시작하기로 하고, 무전기의 할당을 마쳤다.
하지만 전쟁 컨텐츠를 시작하기 하루 전, 시논은 무전기 아이템에 심각한 버그가 있다는 것을 알게 되었다.
바로, 두 플레이어 간 거리가 일정 이상 벌어지면 통신이 두절된다는 것이다.
시논은 이 사실을 알고 자신의 통솔에 문제가 생기는지를 파악하기 위해 특정 시간에 두 플레이어가 통신이 가능한지를 알고 싶어한다.
이 때, 통신이 가능하다는 것은 지휘 사항을 전달할 수 있다는 것으로 간접적으로 연결되는 것도 가능하다.
(예를 들어 1번-2번, 2번-3번 플레이어 간 통신이 가능할 경우 1번과 3번은 통신이 가능한 것으로 한다)
불행 중 다행으로, 이 컨텐츠에 참여하는 플레이어들은 뉴비들이어서 등속도로 움직인다.(앞만 보고 뛴다)
시논은 이러한 가정을 바탕으로 특정 시간에 두 플레이어의 통신가능 여부를 파악하는 프로그램을 부탁하였다.
시논을 도와주자.
입력
입력의 첫줄에 참가자의 명수 N과 무전기의 수 M, 통신가능여부 질문의 개수 Q가 주어진다. (1<=N<=100000, 1<=M<=100000, 1<=Q<=100000)
그 뒤 N개의 줄에는 참가자의 좌표(t=0)와 속도 x, y, vx, vy(1<=x, y<=10000, 1<=vx, vy<=1000) 가 주어진다.
vx, vy 쌍은 모든 플레이어에 대해 다름이 보장된다.(속도가 같은 플레이어는 없다)
그 뒤 M개의 줄에는 무전기로 연결된 플레이어와 통신가능거리 S, E, D(1<=S, E<=N, 1<=D<=10000) 가 주어진다.
거리는 유클리디안 거리로 계산한다. S, E쌍은 모든 무전기에 대해 다름이 보장된다.(두 플레이어를 연결하는 데에 2개 이상의 무전기가 쓰이는 일은 없다)
그 뒤 Q개의 줄에는 시간, 두 플레이어 T, S, E(1<=T<=100000, 1<=S,E<=N)가 주어진다.
출력
Q개의 질문에 대하여 통신이 가능하면 1, 불가능하면 0을 한 줄당 하나씩 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | N<=100, Q<=100 |
| #2 | 30점 | N<=1,000, Q<=1,000 |
| #3 | 50점 | 제한 조건 없음 |
예제
4 4 8
0 0 0 0
0 0 0 1
0 -3 0 2
0 -2 0 2
1 2 3
1 3 1
1 4 4
2 3 3
3 1 2
3 1 3
3 1 4
3 2 3
6 1 2
6 1 3
6 1 4
6 2 3
1
1
1
1
0
0
0
1
3초일 때 통신이 가능한 무전기는 1,3,4번이다. 따라서, 1번-2번, 1번-4번, 2번-3번 플레이어가 연결되므로 모든 플레이어가 연결된다.
6초일 때 통신이 가능한 무전기는 4번 뿐이다. 따라서, 1번-4번 플레이어가 통신이 가능하다.
로그인해야 코드를 작성할 수 있어요.