题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2073
这是一道找规律的题目。给出两点((x1,y1)和(x2,y2)),假设以(0,0)这个起点开始画线。可以发现(0,1)->(1,0),(0,2)-> (2,0),...(0,n)-> (n,0)这些下降的线上才有多个分布的点,而这些点是有规律可循的,任意的点(x,y)的和等于它所处的线上的端点的x和y的和,而且越往线下画,它的x坐标在递增,y坐标在递减。而(1,0)->(0,2),(2,0)->(0,3)...(n,0)->(0,n+1)这些上升的线上是没有点的(除了端点)。
总的来说,算折线长度要分两种情况:1、给出的两点在同一条折线上(即x1+y1 = x2 + y2) 2、给出的两点不在同一条折线上(即x1+y1 != x2 + y2),此时需要分清究竟是哪一个点在前,哪一个点在后。 接下来就是判断经过多少条上升的线和多少条下降的线了,当然,这个判断对于两点不在同一条线上的情况才有的。当算到给出的点在线上时,就计算它跟端点之间的距离。其实我觉得代码有点重复,所以有点啰嗦。但是思路还是比较容易理解的。
1 #include <iostream> 2 #include <math.h> 3 using namespace std; 4 5 double distance (double x1, double y1, double x2, double y2) 6 { 7 return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); 8 } 9 10 int main() 11 { 12 int cas, i, j, k, l; 13 double x1, x2, y1, y2, sum; 14 while (cin >> cas) 15 { 16 while (cas--) 17 { 18 cin >> x1 >> y1 >> x2 >> y2; 19 sum = 0; 20 if (x1 + y1 == x2 + y2) 21 printf("%.3lf\n", distance(x1, y1, x2, y2)); 22 else if (x1 + y1 > x2 + y2) 23 { 24 j = x2 + y2; //分清哪个点在前(首点) 25 sum += distance(x2, y2, j, 0); //该点到它所在线的距离 26 l = x1 + y1; 27 for (k = j; k < l; k++) 28 { 29 sum += distance(k, 0, 0, k+1); //经过多少条上升的线并计算距离 30 if (k+1 < l) 31 sum += distance(0, k+1, k+1, 0); //经过多少条下降的线并计算距离 32 33 } 34 sum += distance(x1, y1, 0, l); //末点到它所在线的距离 35 36 printf("%.3lf\n", sum); 37 } 38 else 39 { 40 j = x1 + y1; 41 sum += distance(x1, y1, j, 0); 42 l = x2 + y2; 43 for (k = j; k < l; k++) 44 { 45 sum += distance(k, 0, 0, k+1); 46 if (k+1 < l) 47 sum += distance(0, k+1, k+1, 0); 48 } 49 sum += distance(x2, y2, 0, l); 50 printf("%.3lf\n", sum); 51 } 52 } 53 } 54 return 0; 55 }