Cod sursa(job #2066336)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 14 noiembrie 2017 21:48:56
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 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 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()
{
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);

	int n;
	scanf("%d", &n);

    double sum_x = 0.0;
	double sum_y = 0.0;
	for(int i = 1; i <= n; ++i) {
		double x, y;
		scanf("%lf %lf", &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 / n;
    solutie.y = sum_y / 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);
        //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;
        }

        dist2 = dist(puncte, n, Ox_dr);
        if(dist0 > dist2) {
            solutie = Ox_dr;
            continue;
        }

        dist3 = dist(puncte, n, Oy_dw);
        if(dist0 > dist3) {
            solutie = Oy_dw;
            continue;
        }

        dist4 = dist(puncte, n, Ox_st);
        if(dist0 > dist4) {
            solutie = Ox_st;
            continue;
        }

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

	printf("%.4lf %.4lf", solutie.x / 1000, solutie.y / 1000);
	return 0;
}