cho.sh

데이터 체커

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

원 이동하기 2 문제를 만들고 만든 데이터가 문제의 조건에 맞는지 확인하는 코드를 작성해야한다.

해당 문제의 데이터는 아래 조건들을 만족해야한다.

  1. 모든 원의 중심 좌표는 xx축 위에 존재해야 한다.
  2. NN개의 원 중 임의의 두 원을 선택했을 때, 교점이 존재하지 않아야 한다. 즉, 하나의 원이 다른 원 안에 존재하거나 외부에 존재한다.

데이터 형식은 원의 개수 NN이랑 각 원의 중심 xx좌표, 원의 반지름 rr만 주어진다. 따라서, 2번 조건을 만족하는지만 확인하면 된다.

주어진 데이터가 해당 조건을 만족하는지 확인해보자.

입력

첫 번째 줄에는 원의 개수 NN이 주어진다.

두 번째 줄부터 N+1N+1번째 줄까지 원의 중심 xx좌표, 원의 반지름 rr이 공백으로 구분되어 주어진다.

출력

데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다.

제한

  • 2≤N≤200,0002 ≤ N ≤ 200,000
  • −1,000,000≤x≤1,000,000-1,000,000 ≤ x ≤ 1,000,000
  • 1≤r≤10,0001 ≤ r ≤ 10,000
  • x,rx, r은 정수

힌트

두 원의 위치관계

두 원의 위치관계를 파악할 때 아래를 이용하면 된다.

원 A의 반지름은 r_Ar\_A, 원 B의 반지름은 r_Br\_B, 원 A와 원 B의 중심 사이의 거리를 dd라고 가정하자.

두 점에서 만난다.한 점에서 만난다.만나지 않는다.
외접내접외부에 있는 경우내부에 있는 경우동심원
∥r_A−r_B∥\<d\<r_A+r_B\|r\_A-r\_B\|\<d\<r\_A+r\_Br_A+r_B=dr\_A+r\_B=d∥r_A−r_B∥=d\|r\_A-r\_B\|=dr_A+r_B\<dr\_A+r\_B\<dd<∥r_A−r_B∥d<\|r\_A-r\_B\|d=0d=0

두 점 사이의 거리

(x_1,y_1)(x\_1, y\_1)와 (x_2,y_2)(x\_2, y\_2) 사이의 거리 dd를 구하는 식은 아래와 같다.

d=(x_1−x_2)2+(y_1−y_2)2d = \sqrt{(x\_1-x\_2)^2+(y\_1-y\_2)^2}