7.标题:螺旋折线
如图p1.png所示的螺旋折线经过平面上所有整点恰好一次。
对于整点(X, Y),我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。
例如dis(0, 1)=3, dis(-2, -1)=9
给出整点坐标(X, Y),你能计算出dis(X, Y)吗?
【输入格式】
X和Y
对于40%的数据,-1000 <= X, Y <= 1000
对于70%的数据,-100000 <= X, Y <= 100000
对于100%的数据, -1000000000 <= X, Y <= 1000000000
【输出格式】
输出dis(X, Y)
【样例输入】
0 1
【样例输出】
3
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms
题意:给定一个点的坐标,要求你求从原点出发,绕折线走(如图),到定点的距离。
分析:如果再添一条直线y=-x,就可以看出其实这是两个相似三角形。
可观察到左下角单边的长度依次为 1 3 5 7 ·······
右上角单边的长度为 2 4 6 8 ·······
所以从第一个三角形到第n个三角形,左下角的三角形单边的边长和为(n*n),右上角的三角形一边的边长和为(n*n+n)。
而各个单边的判断条件可以用数学知识限定。
此外,定点所在的单边上,经过的长度需要单独计算,不过也很简单,注意x,y的正负就行了。
#include<cstdio> int main(){ long long x,y; double sum; while(~scanf("%lld %lld",&x,&y)){//x,y可能达到10的10次方 //根据数学知识判断点处于哪个区域 if(y>=x&&y>=(-x)){ sum=(x+y)+2*((y-1)*(y-1)+(y-1))+2*y*y;//如果点在上边 } else if(y<x&&y>=(-x)){ sum=(x-y)+(x-1)*(x-1)+(x-1)+x*x+x+2*x*x;//如果点在右边 } else if(y<(-x)&&y>=x+1){ sum=(y-(x+1))+2*((-x-1)*(-x-1)+(-x-1))+(-x)*(-x)+(-x-1)*(-x-1);//如果点在左边 } else{ sum=(-y-x)+2*(-y)*(-y)+2*((-y)*(-y)+(-y));//如果点在下边 } printf("%.0lf\n",sum);//x的平方可能超过10^19,所以用double类型 } return 0; }