Rezolvare xOy

Vom prezenta o soluție alternativă a problemei xOy, însă mai ineficientă din punct de vedere al timpului de execuție (de complexitate \(\mathcal{O}(\texttt{VMAX})\), unde \(\texttt{VMAX} = 10^6\)).

Introducere

În problema #xOy , se cere determinarea poziției unui punct \(P\) de coordonate întregi, fiind date punctele \(A\), \(B\), \(C\) (de coordonate întregi) și distanțele \(PA^2\), \(PB^2\), \(PC^2\) (exprimate tot prin numere întregi).

Soluție

Pasul 1

În rezolvarea problemei, vom folosi următoarea proprietate clasică:

Relația lui Leibniz

În triunghiul \(\Delta{}ABC\), cu centrul de greutate în \(G\), pentru orice punct \(P \in \mathcal{P}\) din plan are loc egalitatea:
\[ PG^2 = \frac{1}{3}\left(PA^2 + PB^2 + PC^2\right) – \frac{1}{9}\left(AB^2 + BC^2 + CA^2\right). \]
Demonstrație: Deoarece \(G\) este centrul de greutate al \(\Delta{}ABC\), pentru orice punct \(P \in \mathcal{P}\):
\[ \overrightarrow{PG} = \frac{\overrightarrow{PA} + \overrightarrow{PB} + \overrightarrow{PC}}{3}. \]
Prin ridicare la pătrat, vom avea
\begin{align*}
PG^2 = \overrightarrow{PG} \cdot \overrightarrow{PG} &= \frac{1}{9} (\overrightarrow{PA} + \overrightarrow{PB} + \overrightarrow{PC})^2 \\ &= \frac{1}{9} \left(\sum PA^2 + 2 \sum \overrightarrow{PA} \cdot \overrightarrow{PB}\right) \\ &= \frac{1}{9} \left(\sum PA^2 + \sum(PA^2 + PB^2 – AB^2)\right) \\ &= \frac{1}{3} (PA^2 + PB^2 + PC^2) – \frac{1}{9} (AB^2 + BC^2 + CA^2),
\end{align*}
ceea ce încheie demonstrația.

Pasul 2

Deoarece distanțele \(PA^2\), \(PB^2\), \(PC^2\) sunt date, iar
\[PG^2 = \frac{1}{3}\left(PA^2 + PB^2 + PC^2\right) – \frac{1}{9}\left(AB^2 + BC^2 + CA^2\right),\]
deducem că \(PG^2 = \text{const} \Leftrightarrow PG = \text{const}\). Așadar, din punct de vedere geometric, \(P\) se află pe un cerc \(\mathcal{C}\) de centru \(G\) și rază \(\sqrt{k}\), unde am notat
\[k := PG^2 = \frac{1}{3}\left(PA^2 + PB^2 + PC^2\right) – \frac{1}{9}\left(AB^2 + BC^2 + CA^2\right).\]

Pasul 3

Ne folosi acum de restricțiile problemei, anume că toate cele trei distanțe date și punctele \(A\), \(B\), \(C\) au coordonate întregi. Astfel, numărul
\[k’ := 9k = 3(PA^2 + PB^2 + PC^2) – (AB^2 + BC^2 + CA^2) \in \mathbb{N}.\]
De asemenea, centrul de greutate al triunghiului \(\Delta{}ABC\) are coordonatele:
\begin{cases}
x_G = \dfrac{x_A + x_B + x_C}{3} \in \mathbb{Q}, \\
y_G = \dfrac{y_A + y_B + y_C}{3} \in \mathbb{Q}.
\end{cases}
Apoi \[PG^2 = k \Leftrightarrow (x_P – x_G)^2 + (y_P – y_G)^2 = k \Leftrightarrow (3x_P – x_{G’})^2 + (3y_P – y_{G’})^2 = k’^2,\]
unde am efectuat notațiile:
\begin{cases}
x_{G’} := 3x_G = x_A + x_B + x_C \in \mathbb{Z}, \\
y_{G’} := 3y_G = y_A + y_B + y_C \in \mathbb{Z}.
\end{cases}
Totodată, luând \(x := 3x_P – x_{G’}\) și \(y := 3y_P – y_{G’}\), avem \(x^2 + y^2 = k’\), cu \(x\), \(y\), \(k’ \in \mathbb{Z}\).

Pasul 4

Vom determina o soluție \((x, y) \in \mathbb{Z} \times \mathbb{Z}\) a ecuației \(x^2 + y^2 = k’^2\). Revenind la notațiile efectuate,
\begin{cases}
x_P = \dfrac{x + x_{G’}}{3} \in \mathbb{Z}, \\
y_P = \dfrac{y + y_{G’}}{3} \in \mathbb{Z}.
\end{cases}
Am determinat așadar un posibil punct laticial \(P(x_P, y_P) \in \mathcal{C}\), însă trebuie să mai verificăm dacă distanțele de la \(P\) la punctele \(A\), \(B\) și \(C\) sunt cele date în problemă:
\[PA^2 = D_{PA}^2, PB^2 = D_{PB}^2, PC^2 = D_{PC}^2.\]
Să observăm că este necesar ca \(x + x_{G’} \equiv 0 (\text{mod } 3)\) și \(y + y_{G’} \equiv 0 (\text{mod } 3)\).

Detalii de implementare

Vom folosi o structură Point, prin care vom memora coordonatele unui punct:

struct Point
{
    int x, y;
};

Distanța dintre două puncte

Pentru două puncte \(p(p_x, p_y)\) și \(q(q_x, q_y)\), definim o funcție Dist(p, q) care să calculeze pătratul distanței dintre acestea, dată de formula:
\[(p_x – q_x)^2 + (p_y – q_y)^2 = dx^2 + dy^2,\]
unde: \begin{cases}
\displaystyle{dx = p_x – q_x}, \\
\displaystyle{dy = p_y – q_y}.
\end{cases}

long long Dist(Point &p, Point &q)
{
    int dx = p.x - q.x,
        dy = p.y - q.y;
    return (long long)dx * dx +
           (long long)dy * dy;
}

Funcția de verificare

De asemenea, vom implementa și o funcție TryPoint(x, y) care verifică dacă perechea \((x, y)\) are proprietățile menționate anterior.

void TryPoint(int x, int y)
{
    if((x + G.x) % 3 == 0 && (y + G.y) % 3 == 0)
    {
        P = Point((x + G.x) / 3, (y + G.y) / 3);
        if(Dist(P, A) == PA2 && Dist(P, B) == PB2 && Dist(P, C) == PC2)
        {
            cout << P << '\n';
            exit(0);
        }
    }
}

Găsirea soluției

Vom itera cu x de la \(0\) la \([\sqrt{k}]\) și vom verifica dacă \(k – x^2\) este pătrat perfect. De menționat că va trebui să probăm același lucru și pentru perechile \((-x, -y)\), \((-x, y)\), \((x, -y)\), motiv pentru care vom declara doi vectori dx și dy (având similar cu vectorii de deplasare). La pasul \(0 \leqslant i < 4\), vom valida perechea \(x \cdot \text{dx}[i], y \cdot \text{dy}[i]\).

Cod sursă

#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

const int dx[] = {1, 1, -1, -1},
          dy[] = {1, -1, 1, -1};

struct Point
{
    int x, y;
    Point(int xx = 0, int yy = 0): x(xx), y(yy) {}
    friend istream& operator >> (istream &in, Point &p)
    {
        in >> p.x >> p.y;
        return in;
    }
    friend ostream& operator << (ostream &out, const Point &p)
    {
        out << p.x << ' ' << p.y;
        return out;
    }
};

Point A, B, C, P, G;
int PA2, PB2, PC2;
long long k;

/// Pătratul distanței dintre punctele p și q
long long Dist(Point &p, Point &q)
{
    int dx = p.x - q.x,
        dy = p.y - q.y;
    return (long long)dx * dx +
           (long long)dy * dy;
}

/// Verifică dacă perechea (x, y) convine.
/// Dacă sunt verificate toate condițiile, se afișează
/// coordonatele lui P și se termină execuția programului.
void TryPoint(int x, int y)
{
    if((x + G.x) % 3 == 0 && (y + G.y) % 3 == 0)
    {
        P = Point((x + G.x) / 3, (y + G.y) / 3);
        if(Dist(P, A) == PA2 && Dist(P, B) == PB2 && Dist(P, C) == PC2)
        {
            cout << P << '\n';
            exit(0);
        }
    }
}

int main()
{
    cin >> A >> B >> C
        >> PA2 >> PB2 >> PC2;
    k = 3LL * (PA2 + PB2 + PC2) - (Dist(A, B) + Dist(B, C) + Dist(C, A));
    G = Point(A.x + B.x + C.x, A.y + B.y + C.y);
    for(int x = 0; 1LL * x * x <= k; x++)
    {
        int y = (int)sqrt(k - 1LL * x * x);
        if(1LL * y * y != k - 1LL * x * x)
            continue;
        for(int i = 0; i < 4; i++)
            TryPoint(x * dx[i], y * dy[i]);
    }
    cout << P;
    return 0;
}

Soluția oficială poate fi accesată aici.