Cod sursa(job #2275033)

Utilizator IordachescuAncaFMI Iordachescu Anca Mihaela IordachescuAnca Data 2 noiembrie 2018 19:41:57
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
#include<math.h>
#define T_min 0.0001
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
struct punct
{
    double x;
    double y;
};
punct v[50004],g,p;
int n,i,ok;
double T,solmin,sol;
int di[]={-1,0,1,0}, dj[]={0,1,0,-1};
double distanta(punct a, punct b)
{
    double sol=0;
    sol=(a.x-b.x)*(a.x-b.x);
    sol=sol+(a.y-b.y)*(a.y-b.y);
    return sqrt(sol);
}
double sum(punct a)
{
	int i;
	double suma=0;
	for(i=1;i<=n;++i)
	{
		suma=suma+distanta(a,v[i]);
	}
	return suma;
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        g.x=g.x+v[i].x;
        g.y=g.y+v[i].y;
    }
    g.x=g.x/n;
    g.y=g.y/n;
    solmin=sum(g);
    T=1000;
    while(T>T_min)
    {
        ok=0;
        for(i=0;i<=3;i++)
        {
            p.x=g.x+di[i]*T;
            p.y=g.y+dj[i]*T;
            sol=sum(p);
            if(solmin>sol)
            {
                g=p;
                solmin=sol;
                ok=1;
                break;
            }
        }
        if(ok==0)
        {
            T=T/2;
        }
    }
    fout<<g.x<<" "<<g.y;
    return 0;
}