Cod sursa(job #1438306)

Utilizator DEFINEtelyEngineersUPB Pirtoaca Vasilescu Zamfiratos DEFINEtelyEngineers Data 19 mai 2015 16:39:17
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda last_acm_practice Marime 1.42 kb
#include<iostream>
#include<fstream>
#include<math.h>
#include<iomanip>
using namespace std;
 
#define NMAX 500001
 
struct punct {
    double x,y;
};
 
punct v[NMAX];
 
double dx[]={0,-1.0,0.0,1.0,0.0};
double dy[]={0,0.0,1.0,0.0,-1.0};
 
double dist(punct a, punct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
 
double suma(punct a, int n)
{
    double s;
    int i;
    s=0;
    for(i=1;i<=n;i++)
        s=s+dist(a,v[i]);
    return s;
}
 
int main ()
{
    int n,i,j,ok;
    double step,value,d;
    punct sol,aux,pmin;
    ifstream f("adapost2.in");
    ofstream g("adapost2.out");
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
    f.close();
    sol.x=0;
    sol.y=0;
    for(i=1;i<=n;i++) {
        sol.x=sol.x+v[i].x;
        sol.y=sol.y+v[i].y;
    }
    sol.x=sol.x/n;
    sol.y=sol.y/n;
    step=1000.000;
    for(i=1;i<=40;i++) {
        value=suma(sol,n);
        pmin=sol;
        ok=1;
        for(j=1;j<=4;j++) {
            aux.x=sol.x+dx[j]*step;
            aux.y=sol.y+dy[j]*step;
            d=suma(aux,n);
            if(d<value) {
                value=d;
                pmin=aux;
                ok=0;
				break;
            }
        }
        if(ok) {
			if(i<=20)
				step=step/3;
			else step=step/2;
		}
        sol=pmin;
    }
    g<<fixed;
    g<<setprecision(4)<<sol.x<<" "<<sol.y;
    g.close();
    return 0;
}