Incremental triplet violence + Dynamic programming

The spiral line

The spiral polyline as shown in Figure P1.png passes through all the points on the plane exactly once. For the hour point (X, Y), we define its distance from the origin as dis(X, Y) is the length of the helical polyline segment from the origin to (X, Y).

For example, dis(0, 1)=3, dis(-2, -1)=9

Given the coordinates of the hour (X, Y), can you calculate dis(X, Y)?

[Input format]

X and Y

For 40% of data, -1000 <= X, Y <= 1000 for 70% of data, -100000 <= X, Y <= 100000 for 100% of data, -1000000000 <= X, Y <= 1000000000

[Output format]

Output dis (X, Y)

[Example Input]

0 1

[Example Output]

3

Resource agreement:

Peak memory consumption (including VMS) < 256 MB CPU consumption < 1000ms

Thought analysis

  • This problem is to find the length of a coordinate in the spiral polyline from the origin. The rule can be seen from the above picture:

(2 times x) + (x-y); If x<0, sum = the sum of the perimeters of the first (absolute value of x -1) squares + (-x + y) (2) for the point y>=x and -y>x, if y>0, sum = the sum of the perimeters of the first (absolute value of y -1) squares + 2 * y+ (y + x); If y<0, then length sum = the sum of the perimeters of the square preceding (absolute value of y -1) + 3

  • Note: The two black arrows in the figure above divide the interval into four parts.

Algorithm show

#include <iostream>
using namespace std;
#include <algorithm> 
int main(a)
{
	int x,y;
	cin>>x>>y;
	long long sum = 0;
	
	if((y<x)&&(-y<=x))
	{
		sum+=x>1? (long long) (4* (2+ (abs(x)- 1) * (abs(x)2 -))) :0;// Find the sum of the perimeters of the first n squares
		sum+=(long long)x>0? (4*x+(x-y)):(y-x);	
	}
	else
	{
		sum+=y>1? (long long) (4* (2+ (abs(y)- 1) * (abs(y)2 -))) :0;// Find the sum of the perimeters of the first n squares
		sum+=(long long)y>0? (2*y+y+x):(6*y-y-x);
	} 
	
	cout<<sum<<endl;
	return 0;
}
Copy the code

Global warming BFS non-recursive [blue bridge cup 真题] (c++ implementation)