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

문제

You are given a circle centered at $(0,0)$ and a set of points on the circle's circumference. You need to check whether all the points lie on two quarter circles facing each other created by two perpendicular lines passing through the origin (including its bounds). If they do, the set is said to satisfy the checker-circle property.

The below illustration is an example set of points that satisfies the checker-circle property.

Determine whether a set of points $P$ satisfies the checker-circle property.

입력

The first line of input contains two space-separated integers: $N$, denoting the number of points in the set, and $R$, denoting the circle's radius. ($1 \le N \le 200\,000;$ $1 \le R \le 10^9$)

The $i$-th of the following $N$ lines of input contains two space-separated integers: $x_i$ and $y_i$, such that $$P_i = R\times \frac{(x_i,y_i)}{\sqrt{x_i^2+y_i^2}}.$$ ($-10^9 \le x_i,y_i \le 10^9;$ $(x_i,y_i) \ne (0,0)$)

Note that the set can contain two or more points with the same position.

출력

Output Yes if the set satisfies the checker-circle property and No otherwise.

서브태스크 1 (4점)

Modified constraints apply: $4 \le N \le 2\,000;$ also, $P_1=(0,R),$ $P_2=(R,0),$ $P_3=(0,-R),$ $P_4=(-R,0)$.

서브태스크 2 (30점)

Modified constraints apply: $1 \le N \le 2\,000$.

서브태스크 3 (66점)

Original constraints apply: $1 \le N \le 200\,000$.

예제 입력 1

3 5
-5 -10
10 -5
-5 10

예제 출력 1

Yes

This test corresponds to the Subtask 2.

$$P_1=\left(-\sqrt{5},-2\sqrt{5}\right); \quad P_2=\left(2\sqrt{5},-\sqrt{5}\right); \quad P_3=\left(-\sqrt{5},2\sqrt{5}\right)$$

예제 입력 2

5 5
3 4
4 -3
-3 -4
-5 0
-3 4

예제 출력 2

No

This test corresponds to the Subtask 2.

노트

(For Sogang students:) Note that this problem is an improvised version that matches the format of a problem in a general programming contest. While in the exam, the original scoring was:

  • $40$ points for Subtask 1.
  • $55$ points for Subtask 2.
  • $5$ points for Subtask 3.

채점 및 기타 정보

  • 예제는 채점하지 않는다.