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 \(H\) Holsteins are conveniently numbered \(1 \ldots H\), and his
\(G\) Guernseys are conveniently numbered \(1 \ldots G\)
(\(1 \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 \(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.

Problem credits: Brian Dean

Problem credits: Brian Dean

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\).

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

riseoj 작성

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