Grade 10 · The struct typeCitește în română

Points in the plane

Original: Puncte în plan

O(n²)C++1764 lines1 example

The idea

A point has the coordinates x and y: struct Punct { int x, y; }. The distance between two points is sqrt((x1 - x2)^2 + (y1 - y2)^2). For comparisons we use the squared distance (an integer, with no rounding errors) and take the square root only when printing. n points are read; the point closest to the origin (the first, on ties) and the largest distance between two points, with two decimals, are printed.

Original description (Romanian)

Un punct are coordonatele x și y: struct Punct { int x, y; }. Distanța dintre două puncte este sqrt((x1 - x2)^2 + (y1 - y2)^2). Pentru comparații folosim pătratul distanței (număr întreg, fără erori de rotunjire) și facem radicalul doar la afișare. Se citesc n puncte; se afișează punctul cel mai apropiat de origine (primul, la egalitate) și cea mai mare distanță dintre două puncte, cu două zecimale.

Complexity
O(n * n) for the maximum distance
Grade
Grade 10 (Clasa a X-a)

Examples

Example 1

Input

4
3 4
-1 2
5 0
2 -2

Expected output

-1 2
6.32

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

puncte-in-plan.cpp
/*
 * Titlu: Puncte în plan
 * Clasa: 10
 * Capitol: Tipul struct
 * Descriere: Un punct are coordonatele x și y: struct Punct { int x, y; }. Distanța
 *            dintre două puncte este sqrt((x1 - x2)^2 + (y1 - y2)^2). Pentru comparații
 *            folosim pătratul distanței (număr întreg, fără erori de rotunjire) și
 *            facem radicalul doar la afișare. Se citesc n puncte; se afișează punctul
 *            cel mai apropiat de origine (primul, la egalitate) și cea mai mare
 *            distanță dintre două puncte, cu două zecimale.
 * Complexitate: O(n * n) pentru distanța maximă
 *
 * Exemplu
 * Intrare:
 * 4
 * 3 4
 * -1 2
 * 5 0
 * 2 -2
 * Ieșire:
 * -1 2
 * 6.32
 */
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

struct Punct
{
    int x, y;
};

Punct p[1000];

long long distantaPatrat(Punct a, Punct b)
{
    long long dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> p[i].x >> p[i].y;

    Punct origine = {0, 0};
    int celMaiAproape = 0;
    for (int i = 1; i < n; i++)
        if (distantaPatrat(p[i], origine) < distantaPatrat(p[celMaiAproape], origine))
            celMaiAproape = i;
    cout << p[celMaiAproape].x << ' ' << p[celMaiAproape].y << '\n';

    long long maxim = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (distantaPatrat(p[i], p[j]) > maxim)
                maxim = distantaPatrat(p[i], p[j]);
    cout << fixed << setprecision(2) << sqrt((double)maxim) << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.