스포트라이트의 이동

시간 제한2초메모리 제한512 MB

요약

중심이 다각형 궤도를 따라 움직이는 N개의 스포트라이트가 있을 때, 시엘이 항상 빛이 닿는 영역 안에 있으면서 시작점에서 도착점까지 갈 수 있는지 판정한다.

난이도: 어려움10점 중 8점
유형: 기하, 시뮬레이션, 그래프, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

여우를 닮은 외모와 행동을 가진 아이돌 Ciel은 며칠 뒤 열리는 라이브 콘서트 리허설에 참가한다. 최고의 아이돌이 되기 위해서는 많은 노력이 필요하다!

라이브 무대는 2차원 평면으로 나타낼 수 있다. 무대에는 무대를 비추는 스포트라이트가 N개 있다. i번째 스포트라이트는 반지름 ri인 원 범위에 빛을 비춘다. i번째 스포트라이트가 비추는 빛의 중심은 궤도 Ri를 따라 움직인다. Ri는 닫힌 다각형으로 주어지며, 자기 교차를 포함할 수도 있다. 스포트라이트는 Ri의 첫 번째 꼭짓점에서 움직이기 시작한다. 모든 스포트라이트의 공전 주기는 같다. 각 스포트라이트는 일정한 속력으로 움직이고, 모두 같은 시각에 출발점으로 돌아온다.

리허설에서 Ciel은 무대에 표시된 시작점에서 도착점까지 이동해야 한다. 목표를 이루려면 스포트라이트가 비추는 영역 밖으로 나가면 안 된다. 하지만 시작점에 서 있는 동안에는 스포트라이트의 빛을 받지 않아도 된다. Ciel은 충분히 빠르게 움직일 수 있다고 가정한다. 그녀가 도착점까지 이동할 수 있는지 답하시오.

입력

각 입력 데이터셋은 다음 형식으로 주어진다.

N sx sy ex ey
r1 K1 x11 y11 x12 y12 ... x1K1 y1K1
r2 K2 x21 y21 x22 y22 ... x2K2 y2K2
:
:
rN KN xN1 yN1 xN2 yN2 ... xNKN yNKN

모든 입력은 정수이다. 모든 좌표 정보는 -10,000 ≤ x, y ≤ 10,000을 만족한다. N (1 ≤ N ≤ 100)은 스포트라이트의 개수이다. (sx, sy)와 (ex, ey)는 각각 Ciel이 이동하는 경로의 시작점과 도착점이다. 이어지는 N개의 줄은 각 스포트라이트의 정보다. ri (1 ≤ ri ≤ 100)는 스포트라이트의 반지름이고, Ki (2 ≤ Ki ≤ 10)는 궤도의 꼭짓점 개수이다. 이어서 Ki개의 꼭짓점이 주어진다. 같은 궤도에서 연속한 두 꼭짓점은 서로 다른 위치에 있다. 스포트라이트는 첫 번째 점 (xi1, yi1)에서 두 번째 점 (xi2, yi2)로 이동하고, 다시 세 번째 점 (xi3, yi3)으로 이동하는 식으로 움직인다. Ki번째 점 (xiKi, yiKi)로 이동한 뒤에는 첫 번째 점 (xi1, yi1)으로 돌아가 같은 이동을 반복한다.

스포트라이트 i의 중심과 스포트라이트 j의 중심 사이의 최소 거리를 dij라고 하자. dij는 다음 중 하나를 만족한다.

dij > ri + rj + 0.000001
dij < ri + rj - 0.000001

또한 스포트라이트 i의 중심과 시작점 또는 도착점 사이의 최소 거리를 di라고 하자. di는 다음 중 하나를 만족한다.

di > ri + 0.000001
di < ri - 0.000001

출력

Ciel이 빛이 비추는 영역 밖으로 나가지 않고 도착점까지 이동할 수 있으면 Yes를 한 줄에 출력한다. 그렇지 않으면 No를 출력한다.

예제4

예제 1

입력

2 1 1 9 -1
2 2 1 1 -9 1
1 2 -1 -1 9 -1

예상 출력

Yes

예제 2

입력

2 1 1 9 -1
2 2 1 1 -9 1
1 2 9 -1 -1 -1

예상 출력

No

예제 3

입력

2 11 6 -9 1
6 4 10 5 10 0 5 0 5 5
5 4 -10 0 -10 5 -5 5 -5 0

예상 출력

Yes

예제 4
입력
```
1 1 9999 -1 0
100 2 0 0 0 10000
```
예상 출력
```
Yes
```