#PU670. USACO 2016 December Contest, Gold — Problem 2. Cow Checklist

    ID: 1238 传统题 文件IO:checklist 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec16来源:usaco.orgscoring:equal_test_cases排序

USACO 2016 December Contest, Gold — Problem 2. Cow Checklist

USACO 2016 December Contest, Gold — Problem 2. Cow Checklist

题目描述

Every day, Farmer John walks through his pasture to check on the well-being of each of his cows. On his farm he has two breeds of cows, Holsteins and Guernseys. His HH Holsteins are conveniently numbered 1…H1 \ldots H, and his GG Guernseys are conveniently numbered 1…G1 \ldots G (1≤H≤1000,1≤G≤10001 \leq H \leq 1000, 1 \leq G \leq 1000). Each cow is located at a point in the 2D plane (not necessarily distinct). Farmer John starts his tour at Holstein 1, and ends at Holstein HH. He wants to visit each cow along the way, and for convenience in maintaining his checklist of cows visited so far, he wants to visit the Holsteins and Guernseys in the order in which they are numbered. In the sequence of all H+GH+G cows he visits, the Holsteins numbered 1…H1 \ldots H should appear as a (not necessarily contiguous) subsequence, and likewise for the Guernseys. Otherwise stated, the sequence of all H+GH+G cows should be formed by interleaving the list of Holsteins numbered 1…H1 \ldots H with the list of Guernseys numbered 1…G1 \ldots G. When FJ moves from one cow to another cow traveling a distance of DD, he expends D2D^2 energy. Please help him determine the minimum amount of energy required to visit all his cows according to a tour as described above.

输入格式

The first line of input contains HH and GG, separated by a space. The next HH lines contain the xx and yy coordinates of the HH Holsteins, and the next GG lines after that contain coordinates of the Guernseys. Each coordinate is an integer in the range 0…10000 \ldots 1000.

输出格式

Write a single line of output, giving the minimum energy required for FJ's tour of all the cows.

数据范围

(见题面原文)

样例

样例 1

3 2
0 0
1 0
2 0
0 3
1 3
20
Problem credits: Brian Dean