Cod sursa(job #1403794)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 27 martie 2015 16:26:54
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <cmath>
#define Nmax 50005
#define eps 0.00001

using namespace std;

struct Point
{
    double x,y;
} a[Nmax];
int n;

const int dx[]={-1,0,1, 0};
const int dy[]={ 0,1,0,-1};

inline long double D(Point A)
{
    int i;
    double sol=0;
    for(i=1;i<=n;++i) sol+=sqrt((A.x-a[i].x)*(A.x-a[i].x)+(A.y-a[i].y)*(A.y-a[i].y));
    return sol;
}

int main()
{
    int i;
    double Dist,D1,pasi=200;
    Point P,Q;
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");
    fin>>n;
    for(i=1;i<=n;++i) fin>>a[i].x>>a[i].y;
    P.x=P.y=500; Dist=D(P);
    while(pasi>=eps)
    {
        int ok=0;
        for(int t=0;t<4;++t)
        {
            Q.x=P.x+pasi*dx[t]; Q.y=P.y+pasi*dy[t];
            D1=D(Q);
            if(D1<Dist)
            {
                Dist=D1; P=Q; ok=1; break;
            }
        }
        if(!ok) pasi/=2.0;
    }
    fout<<P.x<<" "<<P.y<<"\n";
    return 0;
}