Cod sursa(job #1758803)

Utilizator cristina_borzaCristina Borza cristina_borza Data 17 septembrie 2016 21:34:09
Problema Adapost 2 Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <fstream>
#include <cmath>

#define se second
#define fi first

using namespace std;

ofstream g ("adapost2.out");

pair <double , double> point[50005];

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

double x = 1024 , y = 1024;

double dist (pair <double , double> a, pair <double , double> b);
double verif (double x, double y);

#define DIM 10000
char buff[DIM];
int poz=0;


void citeste(double &numar)
{
     numar = 0;
     char semn='+';
     while (buff[poz] < '0' || buff[poz] > '9')
     {
          semn = buff[poz];
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     if (buff[poz] == '.')
     {
          double tmp,cnt;
          tmp = 0;
          cnt = 1;
          ++poz;
          while ('0'<=buff[poz] && buff[poz]<='9')
          {
               cnt = cnt/10;
               tmp = tmp + cnt*(double(buff[poz]-'0'));
               if (++poz == DIM)
                    fread(buff,1,DIM,stdin),poz=0;
          }
          numar += tmp;
     }
     if (semn == '-')
          numar = - numar;
}

void read(int &numar)
{
    poz = 0;
    numar = 0;
    while (buff[poz] < '0' || buff[poz] > '9')
        if (++poz == DIM)
            fread(buff,1,DIM,stdin),poz=0;
    while ('0'<=buff[poz] && buff[poz]<='9')
    {
        numar = numar*10 + buff[poz] - '0';
        if (++poz == DIM)
            fread(buff,1,DIM,stdin),poz=0;
    }
}


int main() {
    freopen("adapost2.in" , "r" , stdin);

    read(n);
    for (int i = 1; i <= n; ++i) {
        citeste(point[i].fi) , citeste(point[i].se);
    }

    double d = 1024;
    while (d > 0.0001) {
        double aux1 = verif (x , y);
        int ok = 0;

        for (int i = 1; i <= 4; ++i) {
            double aux2 = verif (x + dx[i] * d , y + dy[i] * d);
            if (aux2 < aux1) {
                x = x + dx[i] * d;
                y = y + dy[i] * d;
                ok = 1;
                break;
            }
        }

        if (!ok) {
            d /= 2;
        }
    }

    g << x << " " << y << '\n';
    return 0;
}

double dist (pair <double , double> a, pair <double , double> b) {
    double aux = (a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se);
    return (double)sqrt((double)(aux));
}

double verif (double x, double y) {
    pair <double , double> p2;
    double ans = 0;

    p2.fi = x;
    p2.se = y;

    for (int i = 1; i <= n; ++i) {
        ans += dist (point[i] , p2);
    }

    return ans;
}