체커 서클 성질

시간 제한1초메모리 제한1024 MB

요약

반지름이 R인 원 위에 있는 N개의 점이 원점을 지나는 수직인 두 직선으로 나뉜 마주 보는 두 사분원 위에 모두 놓이는지 판별합니다.

난이도: 보통10점 중 5점
유형: 기하, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

중심이 $(0,0)$ 이고 반지름이 $R$ 인 원이 있고, 그 원둘레 위에 점들의 집합이 놓여 있다. 원점을 지나고 서로 수직인 두 직선은 원을 네 개의 사분원으로 나눈다. 모든 점이 경계를 포함하여 마주 보는 두 사분원 위에 있는지 확인하라. 그렇다면 이 점 집합은 체커-서클 성질을 만족한다고 한다.

아래 그림은 체커-서클 성질을 만족하는 점 집합의 예이다.

점 집합 $P$ 가 체커-서클 성질을 만족하는지 판별하라.

입력

첫 줄에는 공백으로 구분된 두 정수 $N$ 과 $R$ 이 주어진다( $1 \le N \le 200\,000$ , $1 \le R \le 10^9$ ). $N$ 은 점 집합의 점 개수이고, $R$ 은 원의 반지름이다.

이어지는 $N$ 개의 줄 중 $i$ 번째 줄에는 공백으로 구분된 두 정수 $x_i$ 와 $y_i$ 가 주어진다( $-10^9 \le x_i, y_i \le 10^9$ , $(x_i,y_i) \ne (0,0)$ ). 점은 $P_i = R \times \frac{(x_i,y_i)}{\sqrt{x_i^2+y_i^2}}$ 이다.

같은 위치에 있는 점이 둘 이상 있을 수 있다.

출력

점 집합이 체커-서클 성질을 만족하면 Yes, 그렇지 않으면 No를 출력한다.

힌트

이 문제는 일반 프로그래밍 대회 형식에 맞추어 고친 버전이다. 원래 시험의 배점은 서브태스크 1이 40점, 서브태스크 2가 55점, 서브태스크 3이 5점이었다.

예제2

예제 1
입력
```
3 5
-5 -10
10 -5
-5 10
```
예상 출력
```
Yes
```
예제 2
입력
```
5 5
3 4
4 -3
-3 -4
-5 0
-3 4
```
예상 출력
```
No
```