Cod sursa(job #2081729)

Utilizator karakter98Irimia Robert karakter98 Data 5 decembrie 2017 02:10:39
Problema Adapost 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

FILE* fin;
FILE* fout;

int n;
struct point
{
    double x;
    double y;
}adapost, V[50000];

double computeDistance(point x, point v[], int n)
{
    double sum = 0;
    for(int i = 0; i < n; ++i)
    {
        double deltaX = x.x - v[i].x;
        double deltaY = x.y - v[i].y;
        sum += sqrt(deltaX * deltaX + deltaY * deltaY);
    }
    return sum;
}

int main()
{
    fin = fopen("adapost2.in", "r");
    fout = fopen("adapost2.out", "w");

    double sumX = 0;
    double sumY = 0;
    fscanf(fin, "%d", &n);
    for(int i = 0; i < n; ++i)
        {
            fscanf(fin, "%lf %lf", &V[i].x, &V[i].y);
            sumX += V[i].x;
            sumY += V[i].y;
        }
    adapost.x = sumX / n;
    adapost.y = sumY / n;

    double stepX = 256.0;
    double stepY = 256.0;

    while(stepX > 0.000001)
    {
        double currDist = computeDistance(adapost, V, n);

        adapost.x += stepX;
        double newDist1 = computeDistance(adapost, V, n);

        adapost.x -= 2 * stepX;
        double newDist2 = computeDistance(adapost, V, n);

        double bestDist = min(min(currDist, newDist1), newDist2);

        if(bestDist == currDist)
            {
                stepX /= 2.0;
                adapost.x += stepX;
            }
        else if(bestDist == newDist1)
            adapost.x += 2 * stepX;

        currDist = computeDistance(adapost, V, n);

        adapost.y += stepY;
        newDist1 = computeDistance(adapost, V, n);

        adapost.y -= 2 * stepY;
        newDist2 = computeDistance(adapost, V, n);

        bestDist = min(min(currDist, newDist1), newDist2);

        if(bestDist == currDist)
            {
                stepY /= 2.0;
                adapost.y += stepY;
            }
        else if(bestDist == newDist1)
            adapost.y += 2 * stepY;


    }

    fprintf(fout, "%f %f", adapost.x, adapost.y);

    return 0;
}