有一片无限大的草地,其可以用平面直角坐标系的第一象限表示,坐标系的其余部分均为沙漠.草地上有n只兔子和n个兔穴,每个兔穴仅能容纳一只兔子.
狼是兔子们最大的敌人.每填,每只兔子会在草地上的某个特定位置吃草,当狼来捕食时,兔子们便开始逃跑.当前处在(xy)的兔子,下一步可以到达(x-yy)(xy-x)(x+yy)(xx+y)这四个位置中的任意一个.任何时刻兔子都不能到达沙漠区域(即不能到达在坐标轴上或其他象限内的位置).如果兔子所在的位置下有空着的兔穴,兔子就可以钻进兔穴里,从而躲避狼的追击.古人云"狡兔三窟",兔子们很聪明,虽然他们没有挖到更多的兔穴,但是他们已经商量好,当狼来捕食的时候,不必逃到自己的兔穴,可以临时躲到其它兔子的兔穴.经过不断实践,兔子们发现,当所有兔子到达兔穴的步数总和最小时,兔子们是最安全的,尽管有的兔子可能要跑较多的步数.给出n只兔子吃草的位置,和n个兔穴的位置,请你求出所有兔子到达兔穴的最小步数和.
因版权问题,题目已隐藏.如有需要请私下联系root或nodgd.
第一行为一个正整数n,为兔子的数目和兔穴的数目.
接下来n行,每行两个正整数,描述一只兔子吃草的位置坐标.
接下来n行,每行两个正整数,描述一个兔穴的位置坐标.
数据保证每只兔子可以到的任意的兔穴.
输出仅一行,为一个整数,即所有兔子到达兔穴的最小步数和.
步数为2+2=4,不难验证最优性.
测试点1-2:n=1,K<=60
测试点3-4:n=1,K<=2*109
测试点5-7:n=200,K<=60
测试点8-10:n=200,K<=2*109
测试点11-15:n=10000,K<=60
测试点16-20:n=10000,K<=2*109
update2020.10.08
在保留原来20组数据的情况下,新增20组数据,新增的数据满足如下限制条件: