Soluție HackerRank pentru Sherlock and Geometry, subdomeniul Geometry, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Sherlock and Geometry
- Domeniu: Geometry
- Limbaj: C++14
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
Cerință
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 ≤ T ≤ 30000
1 ≤ R ≤ 2000
-2000 ≤ x_c, y_c ≤ 2000
-5000 ≤ x_i, y_i ≤ 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
In the first case, the triangle is touching the circle. In the second case, it neither touches nor intersects the circle.
Cod sursă
#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;
}