Cod sursa(job #1802621)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 10 noiembrie 2016 15:21:20
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.23 kb

#include <iomanip>
#include <fstream>
#include <math.h>
using namespace std;
ifstream ka("adapost2.in");
ofstream ki("adapost2.out");
 
const int N_MAX = 50000;
 
int n;
 
struct punct
{
    double x, y;
    bool operator < (const punct arg) const
    {
        if(x == arg.x)
            return y < arg.y;
        else
            return x < arg.x;
    }
}puncte[N_MAX + 1];
 
double abs(double t)
{
    if(t < 0)
        return -t;
    else
        return t;
}
 
double patrat(double t)
{
    return t * t;
}
 
double distanta(punct p1, punct p2)
{
    return sqrt(patrat(p1.x - p2.x) + patrat(p1.y - p2.y));
}
 
punct cautare()
{
    punct p;
    p.x = puncte[1].x;
    p.y = puncte[1].y;
    double pas = 1000.0;
    while(pas - 0.0001 > 0)
    {
        punct pp;
        //cout << p.x << " " << p.y << '\n';        
 
        pp.x = p.x + pas;
        pp.y = p.y;
        double dist_min = 3000000000;
        double dist = 0;
        int aia;
        for(int i = 1; i <= n; i++)
            dist += distanta(pp, puncte[i]);
        if(dist < dist_min)
        {
            dist_min = dist;
            aia = 1;
        }
 
        pp.x = p.x;
        pp.y = p.y + pas;
        dist = 0;
        for(int i = 1; i <= n; i++)
            dist += distanta(pp, puncte[i]);
        if(dist < dist_min)
        {
            dist_min = dist;
            aia = 2;
        }
 
        pp.x = p.x - pas;
        pp.y = p.y;
        dist = 0;
        for(int i = 1; i <= n; i++)
            dist += distanta(pp, puncte[i]);
        if(dist < dist_min)
        {
            dist_min = dist;
            aia = 3;
        }
 
        pp.x = p.x;
        pp.y = p.y - pas;
        dist = 0;
        for(int i = 1; i <= n; i++)
            dist += distanta(pp, puncte[i]);
        if(dist < dist_min)
        {
            dist_min = dist;
            aia = 4;
        }
         
        if(aia == 1)
            p.x += pas;
        else if(aia == 2)
            p.y += pas;
        else if(aia == 3)
            p.x -= pas;
        else
            p.y -= pas;
        pas /= 1.6;
    }
    return p;
}
 
int main()
{
    ka >> n;
    for(int i = 1; i <= n; i++)
		ka >> puncte[i].x >> puncte[i].y;
    punct pp = cautare();   
    ki << fixed << setprecision(4) << pp.x << " " << pp.y;
}