시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB220574422.917%

문제

가지를 생산하는 마을에서 와파스와 와이더가 가지 밭의 영역 문제로 다투고 있다. 지나가던 키위새가 두 명을 보며 자신이 제시한 게임을 진행하여 최종 승리자가 밭을 전부 가져가자는 제안을 하였다.

와파스와 와이더는 키위새의 제안을 수락하였고 게임의 규칙은 아래와 같다.

  1. 키위새가 밭에서 서로 다른 세 좌표에 나무 기둥을 $1$개씩 설치한다. 키위새가 설치한 $3$개의 나무 기둥이 일직선 상에 있는 경우는 없다.
  2. 와파스와 와이더는 자신의 차례마다 아래 행동을 시행한다.
    1. 밭에서 나무 기둥이 설치되지 않은 좌표 $(x_i, y_i)$에 나무 기둥 $1$개를 설치한다.
    2. 지금까지 설치된 나무 기둥 중 몇 개를 골라 다각형을 이루도록 실로 두른다.
    3. 키위새가 실로 둘러싸인 다각형 내부 넓이를 계산한다.
    4. 넓이가 $A$보다 같거나 크면 해당 차례의 플레이어가 승리하고 게임은 종료된다.
    5. 넓이가 $A$보다 작으면 행동을 마치고 다음 플레이어의 차례로 넘어간다.
  3. 게임 시작 시 와파스부터 차례가 진행되며, 차례를 번갈아가면서 행동을 진행한다.
  4. $N$번째 차례까지 게임이 끝나지 않으면 무승부로 게임은 종료된다.

플레이어 차례에 일어나는 일

와파스와 와이더는 나무 기둥을 심을 때에는 최적의 방법으로 게임을 진행하지 않지만, 나무 기둥을 선택할 때는 최적의 방법으로 게임을 진행하는 것으로 약속했다. 그러나 키위새는 다각형의 넓이를 계산하는 법을 몰라 다각형의 넓이가 항상 $A$보다 작다는 가정 하에 게임을 계속 진행하게 했다.

여러분이 키위새를 도와 $N$개의 차례가 순서대로 주어졌을 때, 게임 결과를 알아내 보자.

입력

첫째 줄에 차례의 횟수 $N$, 양의 정수 $A$가 공백으로 구분되어 주어진다. $(1 \le N \le 10^5;$ $1 \le A \le 10^{16})$

둘째 줄부터 $3$개의 줄에 걸쳐 키위새가 설치한 나무 기둥의 좌표가 주어진다. 그중 $j$째 줄에는 키위새가 설치한 나무 기둥의 좌표 $x_j$, $y_j$가 공백으로 구분되어 주어진다. 키위새가 설치한 $3$개의 나무 기둥이 일직선 상에 있는 경우는 없다.

다섯째 줄부터 $N$개의 줄에 걸쳐 두 플레이어가 설치한 나무 기둥의 좌표가 주어진다. 그중 $i$째 줄에는 $i$번째 차례의 플레이어가 설치한 나무 기둥의 좌표 $x_i$, $y_i$가 공백으로 구분되어 주어진다.

주어지는 모든 나무 기둥의 좌표는 서로 다르고 모든 $x$좌표와 $y$좌표는 절댓값이 $10^8$을 넘지 않는 정수이다.

출력

와파스가 이기는 경우에는 wapas를, 와이더가 이기는 경우에는 wider를, 무승부의 경우에는 draw를 출력한다.

예제 입력 1

5 16
1 1
1 -1
-1 -1
1 -3
-3 -3
-3 1
-1 3
-1 -5

예제 출력 1

wapas

세 번째 차례인 와파스가 둔 기둥으로 인해 넓이 $16$의 다각형이 만들어지므로 와파스가 승리한다.

예제 입력 2

5 19
2 2
1 -1
-1 3
1 1
3 -1
-3 1
1 5
0 0

예제 출력 2

draw

다섯 번째 차례인 와파스가 기둥을 둘 때까지 넓이가 $19$ 이상인 다각형이 만들어지지 않으므로 무승부로 게임이 종료된다.

출처

Contest > BOJ User Contest > 가지컵 > 2023 가지컵 I번