Question

杭电2073，求代码详解。

甜甜从小就喜欢画图画，最近他买了一支智能画笔，由于刚刚接触，所以甜甜只会用它来画直线，于是他就在平面直角坐标系中画出如下的图形：
甜甜的好朋友蜜蜜发现上面的图还是有点规则的，于是他问甜甜：在你画的图中，我给你两个点，请你算一算连接两点的折线长度（即沿折线走的路线长度）吧。

Input
第一个数是正整数N（≤100）。代表数据的组数。每组数据由四个非负整数组成x1，y1，x2，y2；所有的数都不会大于100。

Output
对于每组数据，输出两点(x1,y1),(x2,y2)之间的折线距离。注意输出结果精确到小数点后3位。

Sample Input
50 0 0 10 0 1 02 3 3 199 99 9 95 5 5 5

Sample Output
1.0002.41410.64654985.0470.000

下面是代码：
#include <stdio.h>
#include <math.h>

int main(void)
{
int i,j,n,x1,x2,y1,y2;
double d[1000],l1,l2;
d[1]=1;
d[0]=0;
for(j=2;j<=1000;j++)
{
d[j]=d[j-1]+sqrt(2.0)*(j-1)+sqrt((double)(j*j+(j-1)*(j-1)));
}
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
l1=d[x1+y1]+sqrt(2.0)*x1;
l2=d[x2+y2]+sqrt(2.0)*x2;
if((l2-l1)>0)
printf("%.3lf\n",l2-l1);
else
printf("%.3lf\n",l1-l2);
}
return 0;
}

Answer 1

首先你要明白d数组的作用，d里面存的是依次是（0,0），（0,1），（0,2），（0,3）。。。到原点（即（0,0））的距离。由于图片上每一点到原点的距离都可用原点该点所在斜线与y轴交点的距离加上该店到交点的距离
例：（1,3）到原点的距离可以算作（0,3）到原点的距离加上（0,3）到（1,3）的距离,而（0,3）到（1,3）的距离可以用其x坐标乘以根号2求得，每一小段是根号2
所以，代码中l1,l2分别表示两点到原点的距离，相减即为两点间的距离，算法真的很精妙。
*注：所有的距离均为折线距离，斜率为-1的直线上的点x,y坐标之和为定值，所以代码中使用d(x+y)计算（0,0）到（0,3）的距离。
******************
纯手打，望采纳！！！！！！！！

追问

能解释一些d数组里是怎么计算出直线与y轴的交点到原点距离的？？？

追答

额。。。不谢！

Answer 2

输入的坐标值都不超过100，所以数组d的长度也不会超过100 + 100 = 200。其他看不出什么问题。