Cod sursa(job #2066232)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 14 noiembrie 2017 20:02:33
Problema Adapost 2 Scor 9
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 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));
}

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

    return sum;
}

long long minim_dist(double a, double b, double c, double d, int &direction)
{
    if(a <= b and a <= c and a <= d) {
        direction = 1;
        return a;
    }

    if(b <= a and b <= c and b <= d) {
        direction = 2;
        return b;
    }

    if(c <= a and c <= b and c <= d) {
        direction = 3;
        return c;
    }

    if(d <= a and d <= b and d <= c) {
        direction = 4;
        return d;
    }
}

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

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

	punct centr_greutate;
	long long sum_x = 0;
	long long sum_y = 0;

	for(int i = 1; i <= n; ++i) {
		sum_x += puncte[i].x;
		sum_y += puncte[i].y;
	}

	centr_greutate.x = sum_x / n;
	centr_greutate.y = sum_y / n;

    punct solutie;
    solutie.x = centr_greutate.x;
    solutie.y = centr_greutate.y;

	int pas = 100;

	while(pas != 1) {
		long long dist1;
		long long dist2;
		long long dist3;
		long long dist4;

		punct Ox_dr = solutie;
		punct Ox_st = solutie;
		punct Oy_up = solutie;
		punct Oy_dw = solutie;

        Ox_dr.x = solutie.x + pas;
        Ox_st.x = solutie.x - pas;
        Oy_up.y = solutie.y + pas;
        Oy_dw.y = solutie.y - pas;

        dist1 = dist(puncte, n, Oy_up);
        dist2 = dist(puncte, n, Ox_dr);
        dist3 = dist(puncte, n, Oy_dw);
        dist4 = dist(puncte, n, Ox_st);

        minim_dist(dist1, dist2, dist3, dist4, direction);

        if(direction == 1) {
            solutie = Oy_up;
        }
        else if(direction == 2) {
            solutie = Ox_dr;
        }
            else if(direction == 3) {
                solutie = Oy_dw;
            }
                else {
                    solutie = Ox_st;
                }
        pas /= 2;
	}

	fout << solutie.x / 1000 << " " << solutie.y / 1000;
	return 0;
}