PTIT013C spoj PTIT - Khoảng cách

Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT013C/

1. Đề bài PTIT013C spoj PTIT

Với hai điểm P(xP,yP) và Q(xQ,yQ) trên mặt phẳng, khoảng cách giữa chúng được tính theo công thức:

d(P,Q) = √(xP-xQ)²+(yP-yQ)².

Nhiệm vụ của bạn là viết chương trình nhập vào 4 số nguyên là tọa độ 2 điểm A,B: xA, yA, xB, yB và tìm điểm M trên trục Ox để giá trị d(M,A) + d(M,B) đạt giá trị nhỏ nhất.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Mỗi bộ test gồm 4 số nguyên xA, yA, xB, yB (có giá trị tuyệt đối < 10⁶).

Output

Với mỗi bộ test, in ra đáp số là phần nguyên của giá trị nhỏ nhất của d(M,A) + d(M,B).

Example

Input:

1
0 1 2 1
Output:

2. Nhận xét PTIT013C spoj PTIT

2 điểm A và B nằm cùng phía hay khác phía của Ox thì cũng cho ra giá trị d(M,A) + d(M,B) là như nhau. nên ta dồn 2 điểm về cùng phía cho dễ tính toán (ta dùng hàm abs trong bài code mẫu pascal). kẻ B’B với B’ là điểm đối xứng của B qua Ox, kẻ B’A, giao điểm của B’A và Ox chính là tọa độ tối ưu của M. như vậy ta chỉ cần tính chiều dài của B’A bằng pytago là dc.

3. Code tham khảo PTIT013C spoj PTIT

a. Code pascal

const   fi='';
type    data=longint;
var
        f:text;
        xa,xb,ya,yb,dxa:int64;
        i,test:data;
        res:int64;

begin
        assign(f,fi); reset(f);
        readln(f,test);
         for i:=1 to test do
                begin
                        readln(f,xa,ya,xb,yb);
                        writeln(trunc(sqrt( sqr(xa-xb)+sqr(-abs(ya)-abs(yb))  ) ) );
                end;
        close(f);
end.

b. Code c++

#include <iostream>
#include <math.h>
using namespace std;

long long d(long long xa,long long ya,long long xb,long long yb)
	{
		return sqrt( (xa-xb)*(xa-xb) + (ya-yb)*(ya-yb) );
	}

int main()
{
	long long t,xA,yA,xB,yB;
	int n; cin >> n;
	for(int i=0;i<n;i++)
	{
		cin >> xA >> yA >> xB >> yB;
		if ( (yA>0 && yB>0) || (yA<0 && yB<0)) t= d(xA,-yA,xB,yB);//AB
		else t= d(xA,yA,xB,yB);
		cout << t <<endl;
		t=0;
	}
	return 0;
}

PTIT013C spoj PTIT – Khoảng cách