USACO 2016 December Contest, Gold
Problem 2. Cow Checklist
Contest has ended.
Log in to allow submissions in analysis mode
Farmer John starts his tour at Holstein 1, and ends at Holstein $H$. 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+G$ cows he visits, the Holsteins numbered $1 \ldots H$ should appear as a (not necessarily contiguous) subsequence, and likewise for the Guernseys. Otherwise stated, the sequence of all $H+G$ cows should be formed by interleaving the list of Holsteins numbered $1 \ldots H$ with the list of Guernseys numbered $1 \ldots G$.
When FJ moves from one cow to another cow traveling a distance of $D$, he expends $D^2$ energy. Please help him determine the minimum amount of energy required to visit all his cows according to a tour as described above.
INPUT FORMAT (file checklist.in):
The first line of input contains $H$ and $G$, separated by a space.The next $H$ lines contain the $x$ and $y$ coordinates of the $H$ Holsteins, and the next $G$ lines after that contain coordinates of the Guernseys. Each coordinate is an integer in the range $0 \ldots 1000$.
OUTPUT FORMAT (file checklist.out):
Write a single line of output, giving the minimum energy required for FJ's tour of all the cows.SAMPLE INPUT:
3 2 0 0 1 0 2 0 0 3 1 3
SAMPLE OUTPUT:
20
Problem credits: Brian Dean