Cod sursa(job #2066420)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 14 noiembrie 2017 23:16:23
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("adapost2.in");
ofstream fout("adapost2.out");

const int Nmax = 5e4 + 10;
int direction;

struct punct {
    double x;
    double y;
}puncte[Nmax];

double dist_a_la_b(punct a, punct b) // distanta dintre 2 puncte in plan
{
    return (double)sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double dist(punct puncte[], int n, punct a) // suma distantelor de la punctul a la cele n puncte din plan
{
    double sum = 0;
    for(int i = 1; i <= n; ++i) {
        sum += dist_a_la_b(a, puncte[i]);
    }

    return sum;
}

int main()
{
    int n;
    fin >> n;

    double sum_x = 0.0;
    double sum_y = 0.0;
    for(int i = 1; i <= n; ++i) {
        double x, y;
        fin >> x >> y;
        puncte[i].x = x * 1000;
        puncte[i].y = y * 1000;
        sum_x += puncte[i].x;
        sum_y += puncte[i].y;
    }

    punct solutie;
    solutie.x = sum_x / double(n);
    solutie.y = sum_y / double(n);

    double pas = 100;

    while(pas > 1) {
        double dist0;
        double dist1;
        double dist2;
        double dist3;
        double dist4;

        punct Ox_dr = solutie;
        punct Ox_st = solutie;
        punct Oy_up = solutie;
        punct Oy_dw = solutie;
        //intializam punctele din cele 4 directii cu semnificatia : Ox_dr -> punctul de pe axa Ox translatat la dreapta cu un pas
        Ox_dr.x = solutie.x + pas;
        Ox_st.x = solutie.x - pas;
        Oy_up.y = solutie.y + pas;
        Oy_dw.y = solutie.y - pas;
        //calculam suma distantelor de la cele 5 puncte cheie la cele n puncte date din plan
        dist0 = dist(puncte, n, solutie);
        dist1 = dist(puncte, n, Oy_up);
        dist2 = dist(puncte, n, Ox_dr);
        dist3 = dist(puncte, n, Oy_dw);
        dist4 = dist(puncte, n, Ox_st);
        //daca inca exista un punct pentru care distanta sa fie mai mica atunci ne mutam in acel punct si continuam cautarea cu acel pas
        if(dist0 > dist1) {
            solutie = Oy_up;
            continue;
        }
        if(dist0 > dist2) {
            solutie = Ox_dr;
            continue;
        }
        if(dist0 > dist3) {
            solutie = Oy_dw;
            continue;
        }
        if(dist0 > dist4) {
            solutie = Ox_st;
            continue;
        }

        pas *= 0.6; // am ajuns intr-un punct pentru care suma distantelor este minima si continuam cautarea injumatatind pasul
    }

    fout << fixed << setprecision(4) << solutie.x / 1000 << " " << solutie.y / 1000;
    return 0;
}