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) 2 +(yP-yQ) 2 . Nhiệm vụ của bạn là viết chương trình nhập vào 4 số ...
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)2+(yP-yQ)2.
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 < 106).
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
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #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; } |