2574. [USACO Dec16]萌化大革命

【题目描述】

公元6666年,11区在当时的国家主席的引导下，爆发了如火如荼的萌化大革命,各地学生热烈响应,其中一部分学生想要见主席,于是他们就来到了天门广场，他们由于政治信仰的不同，被分为H个蕾姆卫兵(a)和G个艾米莉亚卫兵(b)，主席迫切的想要接见这些学生，为了公平，根据先来后到的原则，对于报名的蕾姆卫兵,必须按照$a_1,a_2,......a_H$的顺序进行接见，对于G个报名的艾米莉亚卫兵,必须按照$b_1,b_2,......b_G$的顺序进行接见，即在总共接见的H+G个卫兵中,对于两种卫兵的任意编号$i<j$，接见的顺序编号$c_i$和$c_j$必须满足$c_i<c_j$

每一个卫兵在天门广场有一个二维坐标$(x,y)$,由于$a_1$是香之港の记者，所以主席必须先接见$a_1$，初始位置也在$a_1$,由于$a_H$是德克士，主席要跟他谈笑风生，所以$a_H$必须是主席最后一个接见的学生。

每次离开一个学生去接见另一个学生时,若两个学生的距离为$D$，则主席会减少$D^2$秒的寿命，而作为主席钦定的总理你，则需要帮助主席安排行程，减少主席的寿命流失，因为主席说过，他流失了多少寿命，你就要续上双倍的~

【输入格式】

第一行两个整数H,G,表示两种卫兵的数量

接下来H行每行两个整数，为每个蕾姆卫兵的坐标

接下来G行每行两个整数，为每个艾米莉娅卫兵的坐标

【输出格式】

只有一行一个整数,为最小的损失寿命

【样例输入】

3 2



0 0



1 0



2 0



0 3



1 3 

【样例输出】

  20

【提示】

最优接见顺序:

$a_1$->$b_1$->$b_2$->$a_2$->$a_3$

$(0,0)$->$(0,3)$->$(1,3)$->$(1,0)$->$(2,0)$

耗费为$3^2+1^2+3^2+1^2=20$

其他两种唯二可能的方案:

$(0,0)$->$(0,3)$->$(1,0)$->$(1,3)$->$(2,0)$

耗费为$9+10+9+10=39$

$(0,0)$->$(1,0)$->$(0,3)$->$(1,3)$->$(2,0)$

耗费为$1+10+1+10=22$

数据范围:

对于100%的数据,$1<=H,G<=1000$,横纵坐标是$0....1000$之内的整数

【来源】

USACO 2016-2017 金组第二题