시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)3322100.000%

문제

$N$명의 루노(Runo)들이 2차원 평면 위에서 일을 하고 있다. 오늘 루노들의 일은 두 창고를 오가며 짐을 나르는 것이다.

루노들에게는 $1$번부터 $N$번까지 번호가 붙어있는데, $i$번 루노에게 배정된 두 창고의 위치는 점 $(p_i, q_i)$와 점 $(r_i, s_i)$이다.

루노들은 효율적인 것을 좋아하기 때문에, 각 루노는 자신에게 배정된 두 창고 사이를 최단경로를 따라 이동한다. 즉, 두 창고를 잇는 선분 위에서만 이동한다.

루노들을 관리하는 아인(AIN)이는 루노 하나의 위치가 주어질 때, 그 루노의 번호를 맞힐 수 있는 결정 트리(Decision tree)를 만들려고 한다.

결정 트리를 간략히 소개하면 다음과 같다.

  • 결정 트리는 데이터가 주어질 때 그 데이터에 대해 어떤 의사 결정을 내리는 과정을 트리 형태로 나타낸 것이다.
  • 결정 트리에서의 의사 결정은 트리의 루트 노드에서 출발해 어떤 리프 노드(자식이 없는 노드)에 도착할 때까지 계속해서 자식 노드를 따라 내려가는 방식으로 이루어진다.
  • 결정 트리의 내부 노드들은 결정 노드(Decision node)라고 부르며, 다음에 방문할 자식 노드를 결정하는 규칙을 담고 있다.
  • 결정 트리의 리프 노드들은 종단 노드(Terminal node)라고 부르며, 최종 의사 결정 내용을 담고 있다.

아인이가 만들려는 결정 트리에서 결정 노드와 종단 노드의 정확한 명세는 다음과 같다.

  • 결정 노드
    • 내부 인자로 세 정수 $a$, $b$, $c$를 가지며, 왼쪽 자식 노드와 오른쪽 자식 노드를 가지고 있다.
    • 주어진 위치 $(x,y)$에 대해 $ax+by+c$를 계산한다. 그리고 이 값이 양수라면 왼쪽 자식, 음수라면 오른쪽 자식으로 이동한다.
    • 만약, $ax+by+c$의 값이 정확히 $0$이라면 루노의 번호를 맞히지 못한 것으로 판정하고 결정 과정을 마친다.
  • 종단 노드
    • 내부 인자로 정수 $i$를 가지며, 자식 노드는 없다.
    • 주어진 위치가 $i$번 루노의 것이라고 판단하고 결정 과정을 마친다.

아인이는 각 루노마다 그에 해당하는 종단 노드를 정확히 하나씩 만들려고 한다. 따라서 아인이가 만드는 결정 트리는 $N$개의 종단 노드와 $N-1$개의 결정 노드, 총 $2N-1$개의 노드를 가지게 된다.

아인이와 함께 정확한 결정 트리를 구성해 보자. 정확한 결정 트리란, 모든 루노에 대해 그 루노가 가질 수 있는 어떤 위치가 주어지더라도 주어진 위치가 그 루노의 것이라고 올바르게 판단할 수 있는 결정 트리를 의미한다.

입력

첫 번째 줄에 일하는 루노의 수 $N$이 주어진다.

다음 $N$개의 줄에는 각 루노에게 배정된 두 창고의 정보가 주어진다. 이 중 $i$번째 줄에는 네 정수 $p_i, q_i, r_i, s_i$가 주어지며, 이는 $i$번 루노에게 $(p_i, q_i)$에 있는 창고와 $(r_i, s_i)$에 있는 창고가 배정되었다는 뜻이다.

출력

입력으로 들어온 정보를 따라 정확한 결정 트리를 만들 수 있다면 첫 번째 줄에 Yes를 출력하고, 아니면 No를 출력한다.

Yes를 출력한 경우, 결정 트리를 전위 순회한 순서대로 $2N-1$개의 줄에 노드의 구성을 출력한다.

결정 노드는 ? a b c로 출력해야 하며, $|a|, |b| \leq 10^9, |c| \leq 10^{18}$의 범위를 가지는 정수여야 한다. 주어진 입력에 대해 정확한 결정 트리가 존재한다면 이 제한 안에서 충분히 결정 트리를 구성할 수 있음을 증명할 수 있다.

종단 노드는 ! i로 출력해야 하며, 출력에 $1$ 이상 $N$ 이하의 모든 정수가 $i$로 한 번씩 등장해야 한다.

제한

  • $2 \leq N \leq 250$
  • $|p_i|, |q_i|, |r_i|, |s_i| \leq 10^8$
  • $(p_i, q_i) \neq (r_i, s_i)$

예제 입력 1

2
1 1 1 3
3 1 3 3

예제 출력 1

Yes
? 1 0 -2
! 2
! 1

예제 입력 2

2
0 0 5 5
5 0 0 5

예제 출력 2

No

결정 트리를 어떻게 구성하더라도, $(2.5, 2.5)$가 위치로 주어지면 이것이 $1$번 루노인지 $2$번 루노인지 알 수 없다.

예제 입력 3

4
2 0 2 6
3 2 9 2
7 3 7 9
0 7 6 7

예제 출력 3

No

출처

Contest > AI Network Scholarium > AI Network Scholarium I F번