만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

은제 사슬

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

요약
두 닫힌 폴리라인이 같은 선분을 같은 횟수로 덮는지 판정합니다.
난이도

어려움10점 중 8점

유형
기하, 구현
정답자
아직 제출이 없습니다

문제

지금은 질문할 때가 아니다! 런던 역사 박물관에는 19세기에 빅토리아 여왕 본인이 가졌던 은제 사슬이 전시되어 있다. 자니 잉글리시는 비밀 문서의 몸값으로 이 사슬을 가져다 넘겨야 한다. 자니는 밤에 박물관에 쉽게 숨어들 수 있지만, 도난당한 사슬은 무언가로 대신해 두어야 도난이 빨리 드러나지 않는다. 자니는 다른 사슬을 가지고 있으며, 박물관의 사슬을 자신의 사슬로 바꾸려고 한다.

박물관의 사슬은 고정되어 있다. 이 사슬은 선분을 고리로 삼는 닫힌 꺾은선이다. 자니의 사슬은 책상 위에 놓여 있으며, 이 역시 선분을 고리로 삼는 닫힌 꺾은선이다. 자니는 도난당한 사슬이 있던 자리에 자신의 사슬을 고정했을 때, 박물관의 사슬과 완전히 같은 꺾은선이 되는지 묻는다. 겹치는 부분도 같아야 한다. 박물관의 사슬이 어떤 선분을 여러 번 덮고 있다면, 자니의 사슬도 그 선분을 같은 횟수만큼 덮어야 한다. 자니는 사슬을 고리의 끝에서만이 아니라 임의의 지점에서 구부릴 수 있다.

꺾은선은 자기 자신과 교차할 수 있고, 길이가 0인 고리나 겹치는 고리를 포함할 수 있다.

입력

첫 줄에 박물관의 사슬을 이루는 꺾은선의 꼭짓점 개수 nn이 주어진다 (3≤n≤10003 \le n \le 1000). 다음 nn개 줄에는 첫 번째 꺾은선의 꼭짓점 좌표 xix_i, yiy_i가 순회 순서대로 주어진다 (∣xi∣,∣yi∣≤1000|x_i|, |y_i| \le 1000).

다음 줄에는 자니의 사슬을 이루는 꺾은선의 꼭짓점 개수 mm이 주어진다 (3≤m≤10003 \le m \le 1000). 다음 mm개 줄에는 두 번째 꺾은선의 꼭짓점 좌표 xix_i, yiy_i가 순회 순서대로 주어진다 (∣xi∣,∣yi∣≤1000|x_i|, |y_i| \le 1000).

출력

자니가 자신의 사슬을 박물관의 사슬과 똑같은 방식으로 고정할 수 있으면 Yes를, 그렇지 않으면 No를 한 줄에 출력한다.

예제3

  1. 예제 1

    입력
    3
    0 0
    1 0
    0 1
    3
    1 1
    0 1
    1 0
    
    예상 출력
    Yes
    
  2. 예제 2

    입력
    4
    0 0
    1 0
    1 3
    0 3
    4
    0 0
    2 0
    2 2
    0 2
    
    예상 출력
    Yes
    
  3. 예제 3

    입력
    5
    0 0
    1 0
    1 1
    1 0
    1 1
    3
    0 0
    1 0
    1 1
    
    예상 출력
    No