首页 > 代码库 > UVa 10642 - Can You Solve It?

UVa 10642 - Can You Solve It?

题目:二维平面上的整数点,用路径链接起来(0,0)->(1,0)->(0,1)->(2,0)->..

            给你两点坐标,求两点间步长(在路径上的距离)。

分析:简单题。

            我们发现点是按照x+y的递增序,且y的递增序(x+y相同时)排列的;

            所以每个点对应的路径上的位置为:(x+y)*(x+y+1)/ 2 + y。

说明:注意使用long long防止数据溢出。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
	int T,x1,y1,x2,y2;
	while (~scanf("%d",&T))
	for (int t = 1 ; t <= T ; ++ t) {
		scanf("%d%d%d%d",&y1,&x1,&y2,&x2);
		
		long long n = (x1+y1)*(x1+y1+1LL)/2LL+y1;
		long long m = (x2+y2)*(x2+y2+1LL)/2LL+y2;
		
		printf("Case %d: %lld\n",t,m-n);
	}
    return 0;
}


UVa 10642 - Can You Solve It?