Soluție HackerRank pentru House Location, subdomeniul Geometry, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: House Location
- Domeniu: Geometry
- Limbaj: C++14
Challenge: House Location
Scor cont: 80.0 / 80
Submission status: Accepted
Submission score: 1.0
Submission ID: 464762482
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/house-location/problem
Cerință
Adam and Martha are planning to leave the city after their retirement and build a house in a huge land belonging to their family. To keep everyone happy, they want to build the house at a location having distance _a*d1_ from aunt Kimberly's house, where _a_ is some ratio and _d1_ is the distance of that location to uncle Bob's house. Also, the house should be at a distance _b*d2_ from uncle Jack's house where b is some ratio and _d2_ is the distance of the location to aunt Janet's house.
You need to help them find the location of their house.
Input Format
The first line of input contains two integers a and b (the ratios above). In the next four lines, there are 4 pairs of integers that indicate the coordinates of Kimberly's, Bob's, Jack's, and Janet's houses, respectively.
Output Format
You must output the coordinate of house with exactly two points after decimal point (rounded to closest one hundredth). If there is no location satisfying the above constraints, output Impossible! If there are more than one possible locations, output a location with minimum x-coordinate and among the ones having the minimum x-coordinate, a location with minimum y-coordinate.
Constraints
1 < a, b <= 1000
-1000 <= all input coordinates <= 1000
Sample Input
<pre>
3 4
4 0
0 0
-2 -4
-2 -1
</pre>
Sample Output
<pre>-2.00 0.00</pre>
Explanation
As required, the point (-2.00, 0.00) has distance 2 from Bob's house and distance 3*2=6 from Kimberly's house. It also has distance 1 from Janet's house and distance 4*1=4 from Jack's house.
Cod sursă
#include <bits/stdc++.h>
using namespace std;
struct Pt {
long double x, y;
};
struct Circle {
Pt c;
long double r;
};
static const long double EPS = 1e-10L;
Circle apollonius(const Pt& A, const Pt& B, long double k) {
// |P-A| = k |P-B|, k != 1 (here k>1 by constraints)
long double k2 = k * k;
long double den = 1.0L - k2;
long double D = 2.0L * (k2 * B.x - A.x) / den;
long double E = 2.0L * (k2 * B.y - A.y) / den;
long double F = (A.x * A.x + A.y * A.y - k2 * (B.x * B.x + B.y * B.y)) / den;
Pt c{-D / 2.0L, -E / 2.0L};
long double r2 = c.x * c.x + c.y * c.y - F;
if (r2 < 0 && r2 > -1e-8L) r2 = 0;
Circle out{c, sqrtl(max((long double)0.0L, r2))};
return out;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long double a, b;
if (!(cin >> a >> b)) return 0;
Pt K, B, J, T; // Kimberly, Bob, Jack, Janet
cin >> K.x >> K.y;
cin >> B.x >> B.y;
cin >> J.x >> J.y;
cin >> T.x >> T.y;
Circle c1 = apollonius(K, B, a);
Circle c2 = apollonius(J, T, b);
vector<Pt> cand;
long double dx = c2.c.x - c1.c.x;
long double dy = c2.c.y - c1.c.y;
long double d = hypotl(dx, dy);
if (d < EPS) {
if (fabsl(c1.r - c2.r) < 1e-8L) {
// Same circle: infinitely many points; lexicographically minimum point.
cand.push_back({c1.c.x - c1.r, c1.c.y});
}
} else {
if (d <= c1.r + c2.r + 1e-8L && d + min(c1.r, c2.r) + 1e-8L >= max(c1.r, c2.r)) {
long double x = (c1.r * c1.r - c2.r * c2.r + d * d) / (2.0L * d);
long double h2 = c1.r * c1.r - x * x;
if (h2 < 0 && h2 > -1e-8L) h2 = 0;
if (h2 >= -1e-8L) {
long double h = sqrtl(max((long double)0.0L, h2));
long double ux = dx / d, uy = dy / d;
Pt p{c1.c.x + x * ux, c1.c.y + x * uy};
Pt i1{p.x - h * uy, p.y + h * ux};
Pt i2{p.x + h * uy, p.y - h * ux};
cand.push_back(i1);
if (fabsl(i1.x - i2.x) > 1e-8L || fabsl(i1.y - i2.y) > 1e-8L) cand.push_back(i2);
}
}
}
if (cand.empty()) {
cout << "Impossible!\n";
return 0;
}
auto better = [](const Pt& a, const Pt& b) {
if (fabsl(a.x - b.x) > 1e-9L) return a.x < b.x;
return a.y < b.y;
};
Pt best = cand[0];
for (size_t i = 1; i < cand.size(); ++i) {
if (better(cand[i], best)) best = cand[i];
}
double ox = (double)best.x;
double oy = (double)best.y;
if (fabs(ox) < 0.0005) ox = 0.0;
if (fabs(oy) < 0.0005) oy = 0.0;
cout.setf(std::ios::fixed);
cout << setprecision(2) << ox << ' ' << oy << '\n';
return 0;
}