问题描述:
小W是一个宅男,喜欢发呆,并幻想一些不切实际的事情。今天,小W又开始做他的白日梦了。他梦见他被困在了一条隧道里,周围漆黑一片。作为一个宅男,小W自然地掏出了手机,打开定位系统,确定了他的位置。又由此在网上搜索到了关于隧道的信息。这条隧道是由一个点向外,呈六角螺旋形展开,并且没有其他的支路。*小的一圈每条边的长度都是1米,边长向外依次增大到2,3…米,如下图所示。
输入数据以一个整数T<104开头,表示测试数据组数。以下每行为一组测试数据,包括4个整数X1,Y1,X2,Y2,描述了小W所在的位置和出口位置的坐标。所有坐标的**值不超过1018,并保证答案不超出64位有符号整数的表示范围。
输出对于每组测试数据输出一行,一个整数,表示小W所在的位置和出口的距离。
样例输入:
2
1 0 0 1
1 1 2 0
样例输出:
2
9
解题思路:
本题是一个典型的数学模拟题,如下图所示(*好自己在题干图的基础上再多画几层,这有助于理解),我们可以观察到每一圈的长度是一个公差为6的等差数列(7,13,19,25…),那么要计算两个点之间的距离,其实只要知道它们在自己所属那一圈行走的距离以及它们之间相差了几圈即可,可以通过等差数列求和公式计算出相差圈数所代表的距离。
那么,我们可以把整个求解过程分为三步:
1.求出起点和终点分别位于哪一层,用getLayerOfPoint()这个函数来实现。
2.求出起点和终点在它们所在那一层上运动的距离,用getPointDisOfLayer()这个函数来实现。
3.根据等差数列求和公式、两点之间相差的层数以及第2步中所计算出的距离来求解*后的结果。
特别需要注意的是:
1.本题中的起点并不一定位于终点的前面,即它们是可以反向的,所以我们在第3步之前若遇到起点位于终点之后的情况,应该交换它们两个的位置。
2.本题计算距离需要求**值,但abs()函数无法求解long long型的**值,需要自己实现一个求解**值的方法。
代码实现:
总结:
这题*开始做的时候,踩了很多的坑。在某些地方不小心使用了int型导致数值小的用例可以通过,程序逻辑没问题,但是一直WA。后来试了很多较大的数据,发现是没有使用long long型变量。同时,判断点位于哪个象限时,应该对x与y分别进行判断,而不是使用乘法判断,乘法可能会导致计算结果超出long long所能表示的范围。*好的办法还是自己多画一下这个图,对过程自然而然就清楚了。