HackerRank Geometry – Sherlock and Geometry

Challenge: Sherlock and Geometry

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464757208

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/sherlock-and-geometry/problem

Cerinta

Watson gives a circle and a triangle in a 2-dimensional plane to Sherlock. Sherlock has to tell if they intersect/touch each other.   
The circle is centered at $(x_c,y_c)$ and has radius $R$.   

**Input Format**  
The first line contains $T$, the number of test cases.  
Each test case consists of $x_c$, $y_c$ and $R$ in one line.  
The next three lines each contains $x_i, y_i$ denoting the vertices of the triangle.   

**Output Format**   
For each test case, print `YES` if the triangle touches or intersects the circle; otherwise, print `NO`.   

**Constraints**    
$1 \le T \le 30000$  
$1 \le R \le 2000$  
$-2000 \le x_c, y_c \le 2000$  
$-5000 \le x_i, y_i \le 5000$    
**Note:** There will be no degenerate triangles (i.e. triangles with area 0)  

**Sample Input**  

	2
    0 0 10
    10 0
    15 0
    15 5
    0 0 10
    0 0
    5 0
    5 5
    
**Sample Output**    

	YES
    NO

**Explanation**   
![image](https://hr-challenge-images.s3.amazonaws.com/2538/2538a.jpg)
![image](https://hr-challenge-images.s3.amazonaws.com/2538/2538b.jpg)  
In the first case, the triangle is touching the circle. In the second case, it neither touches nor intersects the circle.

Cod sursa

#include <bits/stdc++.h>
using namespace std;

struct Pt {
    long double x, y;
};

static inline long double dot(long double ax, long double ay, long double bx, long double by) {
    return ax * bx + ay * by;
}

bool segmentIntersectsCircle(const Pt& A, const Pt& B, const Pt& C, long double r) {
    long double dx = B.x - A.x;
    long double dy = B.y - A.y;
    long double fx = A.x - C.x;
    long double fy = A.y - C.y;

    long double a = dot(dx, dy, dx, dy);
    long double b = 2.0L * dot(fx, fy, dx, dy);
    long double c = dot(fx, fy, fx, fy) - r * r;

    long double D = b * b - 4.0L * a * c;
    const long double EPS = 1e-12L;
    if (D < -EPS) return false;
    if (D < 0) D = 0;

    long double sq = sqrtl(D);
    long double t1 = (-b - sq) / (2.0L * a);
    long double t2 = (-b + sq) / (2.0L * a);

    auto inside = [&](long double t) {
        return t > -EPS && t < 1.0L + EPS;
    };

    return inside(t1) || inside(t2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        Pt C;
        long double r;
        cin >> C.x >> C.y >> r;

        Pt p[3];
        for (int i = 0; i < 3; ++i) cin >> p[i].x >> p[i].y;

        bool ok = false;
        for (int i = 0; i < 3; ++i) {
            Pt A = p[i];
            Pt B = p[(i + 1) % 3];
            if (segmentIntersectsCircle(A, B, C, r)) {
                ok = true;
                break;
            }
        }

        cout << (ok ? "YES" : "NO") << '\n';
    }

    return 0;
}