杭电ACM 这题做完 我的大脑深呼吸了30秒啊！！！有木有可以想出简洁版的 讨论讨论吧
甜甜从小就喜欢画图画，最近他买了一支智能画笔，由于刚刚接触，所以甜甜只会用它来画直线，于是他就在平面直角坐标系中画出如下的图形：甜甜的好朋友蜜蜜发现上面的图还是有点规则的，于是他问甜甜：在你画的图中，我给你两个点，请你算一算连接两点的折线长度（即沿折线走的路线长度）吧。
Input
第一个数是正整数N（≤100）。代表数据的组数。
每组数据由四个非负整数组成x1，y1，x2，y2；所有的数都不会大于100。
Output
对于每组数据，输出两点(x1,y1),(x2,y2)之间的折线距离。注意输出结果精确到小数点后3位。
Sample Input
public static Scanner input=new Scanner(System.in);
public static float result=0;//思路，算出每个坐标到原点的距离，然后求出两者距离之差即最终距离
public static void main(String[] args) {
// 输入用户需要计算的坐标
System.out.println("Sample Input");
int x1=input.nextInt();
int y1=input.nextInt();
int x2=input.nextInt();
int y2=input.nextInt();
float wolk1=f(x1,y1,x1,y1);//第一个坐标到（0,0）的距离
result=0;
float wolk2=f(x2,y2,x2,y2);//第二个坐标到（0,0）的距离
//测试数据
System.out.println(wolk1);
System.out.println(wolk2);
result=0;//两点的距离就等于两个点分别到零的距离之差
if(wolk1>wolk2){
result=wolk1-wolk2;
}
else if(wolk1<WOLK2){
result=wolk2-wolk1;
}
else if(wolk1==wolk2){
result=0;
}
System.out.println("Sample Output");
System.out.println("4--->"+result);
}
public static float f(int x,int y,int m,int n){//表示它需要走的长度
if(x==0 && y==0){//如果已经是原点，那么就直接跳出递归 返回距离为0
return 0;
}
else if(y<x && x!=0){//如果纵坐标为0,横坐标不为0
y+=x;//将x的值赋给y;然后再进行下边的计算
}
if(y==1){//如果y=1时，即到了跳出递归的时候，
double num=Math.sqrt(2);
if(m!=0){//考虑到x不为零的情况
result=result+(float)(m*num);//如果x横坐标不等于零的时候，还要加上x倍的2的平方根
// System.out.println("2--->"+result);
}
result=result+1;//最后一步就到（0,0)
// System.out.println("3--->"+result);
return result;//返回结果
}
int num1=y*y+(y-1)*(y-1);//直线三角形的 斜线距离的平方
int num2=(y-1)*(y-1)+(y-1)*(y-1);//等腰三角形的斜线距离的平方
result+=Math.sqrt(num1)+Math.sqrt(num2);//平方根后相加的距离
System.out.println("1--->"+result);
x--;//横坐标--
y--;//纵坐标--
return f(x,y,m,n);
}
}
[ 本帖最后由 highness 于 2013-4-22 10:51 编辑 ]
----------------解决方案--------------------------------------------------------
这道题递推就行，不用递归
程序代码：
import java.util.Scanner;
public class test {
public static void main(String[] args) {
Scanner read = new Scanner(System.in);
int n = read.nextInt();
while (n-- != 0) {
int x1 = read.nextInt();
int y1 = read.nextInt();
int x2 = read.nextInt();
int y2 = read.nextInt();
if (x1 + y1 < x2 + y2) {
System.out.println(Get(x1, y1, x2, y2));
} else {
System.out.println(Get(x2, y2, x1, y1));
}
}
}
public static double Get(int x1, int y1, int x2, int y2) {
int m = x1 + y1;
int n = x2 + y2;
double result = x2 * Math.sqrt(2);
for (;m < n;++m) {
result += m * Math.sqrt(2);
result += Math.sqrt(m*m + (m+1)*(m+1));
}
return result - x1 * Math.sqrt(2);
}
}
public class test {
public static void main(String[] args) {
Scanner read = new Scanner(System.in);
int n = read.nextInt();
while (n-- != 0) {
int x1 = read.nextInt();
int y1 = read.nextInt();
int x2 = read.nextInt();
int y2 = read.nextInt();
if (x1 + y1 < x2 + y2) {
System.out.println(Get(x1, y1, x2, y2));
} else {
System.out.println(Get(x2, y2, x1, y1));
}
}
}
public static double Get(int x1, int y1, int x2, int y2) {
int m = x1 + y1;
int n = x2 + y2;
double result = x2 * Math.sqrt(2);
for (;m < n;++m) {
result += m * Math.sqrt(2);
result += Math.sqrt(m*m + (m+1)*(m+1));
}
return result - x1 * Math.sqrt(2);
}
}
----------------解决方案--------------------------------------------------------
上面代码忽略了在同一条线的情况，这样处理就可以了
程序代码：
public static boolean judge(int x1, int y1, int x2, int y2) {
if (x1 + y1 < x2 + y2) return true;
if (x1 + y1 > x2 + y2) return false;
return x1 < x2;
}
[ 本帖最后由 azzbcc 于 2013-4-22 13:39 编辑 ]
----------------解决方案--------------------------------------------------------
回复 2楼 azzbcc
果然 如果没有最后一个判断方法，如果一天线就会有负数结果出现。好像看起来蛮简洁的 不过还是要多酝酿一下思路，呵呵 谢啦，果然讨论一下还是蛮有效果的 ----------------解决方案--------------------------------------------------------