HackerRank Geometry – House Location – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

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

Cerinta

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 sursa

#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;
}

HackerRank Geometry – House Location