Cod sursa(job #1044606)

Utilizator tavi.belu1994FMI Belu Andrei Octavian tavi.belu1994 Data 30 noiembrie 2013 04:41:43
Problema Adapost 2 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define NMAX 51000
FILE *f,*g;
using namespace std;

int dl[]={-1, 1, 0, 0};
int dc[]={0, 0, -1, 1};
double sum;
int N;

struct point{
    double x,y;
};
point fin;
point V[NMAX];

void read()
{
    fscanf(f,"%d",&N);
    for(int i=1 ; i<=N ; i++)
    {
        fscanf(f,"%lf%lf\n",&V[i].x,&V[i].y);
    }
}

double dist(point a, point b)
{
    double d;
    d=sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
    return d;
}

void centru(point V[NMAX], int N, point &a)
{
    a.x = 0;
    a.y = 0;
    for(int i=1; i<=N ; i++)
    {
        a.x += V[i].x;
        a.y += V[i].y;
    }
    a.x = a.x/N * 1.000;
    a.y = a.y/N * 1.000;
    double newsum=0;
    for(int j=1 ; j<=N ; j++)
    {
        newsum += dist(a,V[j]);
    }
    sum = newsum;
    fin = a;
}

double suma(point V[NMAX], point b)
{
    double newsum=0;
    for(int j=1 ; j<=N ; j++)
    {
        newsum += dist(V[j],b);
    }
    return newsum;
}

void solve(point V[NMAX], point a, double p)
{
    while(p>0.001)
    {
        bool sem=0;
        for(int i=0; i<4 && !sem ; i++)
        {
            point b;
            b.x = a.x + dl[i] * p;
            b.y = a.y + dc[i] * p;
            double newsum=suma(V,b);
            if( newsum < sum )
            {
                sem = 1;
                sum = newsum;
                fin = b;
                solve(V,b,p);
            }
        }
        p = p/2;
    }
}


int main()
{
    f=fopen("adapost2.in","r");
    g=fopen("adapost2.out","w");
    read();
    point a;
    centru(V,N,a);
    fin = a;
    solve(V,a,100);
    fprintf(g,"%lf %lf",fin.x,fin.y);
    fclose(f);
    fclose(g);
    return 0;
}