RiseOJ – 소 점검 목록

설명

농부 존은 매일 목초지를 걸으며 소들 각각의 안녕을 살핀다. 그의 농장에는 홀스타인과 건지, 두 품종의 소가 있다. $$H$$ 마리의 홀스타인은 $1 \ldots H$ 로, $$G$$ 마리의 건지는 $1 \ldots G$ 로 번호가 매겨져 있다( $1 \leq H \leq 1000, 1 \leq G \leq 1000$ ). 각 소는 2차원 평면 위의 한 점에 위치한다(서로 다른 점일 필요는 없다).

농부 존은 홀스타인 1번에서 순회를 시작해 홀스타인 $$H$$ 번에서 끝낸다. 그는 도중에 모든 소를 방문하려 하며, 지금까지 방문한 소들의 점검 목록을 관리하기 편하도록 홀스타인과 건지를 각각 번호 순서대로 방문하고 싶다. 그가 방문하는 전체 $$H+G$$ 마리의 소 수열에서, $1 \ldots H$ 로 번호가 매겨진 홀스타인들은 (연속일 필요는 없는) 부분 수열로 나타나야 하고, 건지들도 마찬가지이다. 다시 말해, 전체 $$H+G$$ 마리 소의 수열은 $1 \ldots H$ 번호의 홀스타인 목록과 $1 \ldots G$ 번호의 건지 목록을 서로 끼워 넣어(interleave) 만든 것이어야 한다.

농부 존이 한 소에서 다른 소로 거리 $$D$$ 만큼 이동하면 $$D^2$$ 의 에너지를 소모한다. 위와 같은 순회 방식으로 모든 소를 방문하는 데 필요한 최소 에너지를 구해 존을 도와주자.

문제 출제: 브라이언 딘(Brian Dean)

제약

문제 출제: 브라이언 딘(Brian Dean)

입력 형식

입력의 첫째 줄에 $$H$$ 와 $$G$$ 가 공백으로 구분되어 주어진다.

다음 $$H$$ 개의 줄에는 $$H$$ 마리 홀스타인의 $$x$$ , $$y$$ 좌표가 주어지고, 그다음 $$G$$ 개의 줄에는 건지들의 좌표가 주어진다. 각 좌표는 $0 \ldots 1000$ 범위의 정수이다.

출력 형식

농부 존이 모든 소를 순회하는 데 필요한 최소 에너지를 한 줄에 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 checklist.in · 출력을 쓸 파일 checklist.out

예제 1

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > December > Gold

올림피아드 > USACO > 2016-2017 > December > Gold

태그

JudgeUSACO

소 점검 목록

평가 및 의견

풀이 제출