Tìm điểm trong Tam giác gần với 1 điểm cho trước nhất

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 977M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Jerry học đến tọa độ Đề-các vuông góc 2 chiều, Cô giáo dạy Jerry cách tính diện tích tam giác tạo bởi 3 điểm A(xA,yA), B(xB, yB), C(xC, yC) theo công thức

\[{{S}_{\Delta ABC}}=\frac{1}{2}\,\,\,\left| \,\left( xB-xA \right)(yC-yA)-\left( xC-xA \right)(yB-yA)\, \right|\]

Nhưng bài thi học kỳ cô giáo lại cho 3 điểm A(xA,yA), B(xB, yB), C(xC, yC) và một điểm M(xM, yM). Nhiệm vụ của Jerry là tìm một điểm nằm trong tam giác nhưng gần điểm M nhất, do áp dụng kiến thức chưa được tốt Jerry nhờ các bạn lập trình giúp Jerry bài này nhé

Input

Dòng 1 là số các trường hợp kiểm thử q (1< q <10), tiếp theo q dòng là từng trường hợp kiểm thử.

Mỗi trường hợp kiểm thử gồm 8 số thực có giá trị tuyệt đối không vượt quá 10^4 lần lượt là tọa độ của A, B, C, M

Output

Gồm q dòng mỗi dòng gồm hai số thực với độ chính xác 3 chữ số sau dấu chấm thập phân là tọa độ của điểm M cần tìm

Ví dụ

Input

2
0.0 0.0 2.0 0.0 0.0 1.0 1.0 0.0 
0.0 1.0 3.0 1.0 0.0 4.0 9.0 0.0

Output

1.000 0.000
3.000 1.000

Giải thích: Với test đầu thì M nằm trong tam giác nên điểm cần tìm là M

tichpx

Comments


  • 0
    NGUYENTIENDATCNTTVA2  commented on Feb. 8, 2022, 10:29 a.m. ← edited 
    #include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> Point;
#define x first
#define y second

double square_distance(Point A, Point B)
{
    return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}
Point nearest(Point A,Point B, Point M)
{
    while(fabs(A.x-B.x)>1e-4 || fabs(A.y-B.y)>1e-4)
    {
        Point C((A.x+B.x)/2,(A.y+B.y)/2);
        if(square_distance(A,M)>square_distance(B,M)) A=C;
        else B=C;
    }
    return A;
}
double area(Point A, Point B,Point C)
{
    return fabs((B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y))/2;
}
int main()
{
    cout<<setprecision(3)<<fixed;
    int test;
    cin>>test;
    while(test--)
    {

    Point A,B,C,M,D,E,F;
    cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>M.x>>M.y;
    if(area(A,B,C)==area(A,B,M)+area(B,C,M)+area(C,A,M)) cout<<M.x<<" "<<M.y<<"\n ";
    else
    {
        D=nearest(A,B,M);
        E=nearest(A,C,M);
        F=nearest(C,B,M);
        if(square_distance(D,M)>square_distance(E,M)) D=E;
        if(square_distance(D,M)>square_distance(F,M)) D=F;
        cout<<D.x<<" "<<D.y<<"\n";
    }
}
}