Cod sursa(job #2447994)

Utilizator raduandreicaRadu Andreica raduandreica Data 15 august 2019 14:07:34
Problema Adapost 2 Scor 37
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("adapost2.in"); ofstream fout("adapost2.out");

class punct
{
public:
    float x , y;
    punct()
    {}
    punct(float a , float b)
    {
        this->x = a;
        this->y = b;
    }
    float dist(punct a)
    {
        return(sqrt((this->x - a.x)*(this->x - a.x) + (this->y - a.y)*(this->y - a.y)));
    }
};

int n;
vector <punct> v(50000);

punct cautbin(float x , float y , float dist , float sum)
{
    if(dist <= 0.00075)
    {
        punct a(x , y);
        return a;
    }

    float sumxlow = 0;
    punct xlow(x  - dist , y);
    for(int i=0 ; i<n ; i++)
        sumxlow = sumxlow + xlow.dist(v[i]);

    float sumylow = 0;
    punct ylow(x , y - dist);
    for(int i=0 ; i<n ; i++)
        sumylow = sumylow + ylow.dist(v[i]);

    float sumxhigh = 0;
    punct xhigh(x + dist , y);
    for(int i=0 ; i<n ; i++)
        sumxhigh = sumxhigh + xhigh.dist(v[i]);

    float sumyhigh = 0;
    punct yhigh(x , y + dist);
    for(int i=0 ; i<n ; i++)
        sumyhigh = sumyhigh + yhigh.dist(v[i]);

    float m = min({sumxlow , sumylow , sumxhigh , sumyhigh});
    if(sum <= m)
        return cautbin(x , y , dist/1.35 , sum);
    if(sumxlow == m)
        return cautbin(xlow.x , xlow.y , dist/1.35 , sumxlow);
    if(sumylow == m)
        return cautbin(ylow.x , ylow.y , dist/1.35 , sumylow);
    if(sumxhigh == m)
        return cautbin(xhigh.x , xhigh.y , dist/1.35 , sumxhigh);
    if(sumyhigh == m)
        return cautbin(yhigh.x , yhigh.y , dist/1.35 , sumyhigh);
}
int main()
{
    fin >> n;
    for(int i=0 ; i<n ; i++)
        fin >> v[i].x >> v[i].y;
    float s = 0;
    punct a(0 , 0);
    for(int i=0 ; i<n ; i++)
        s = s + a.dist(v[i]);
    punct ans = cautbin(0 , 0 , 500 , s);
    fout << ans.x << " " << ans.y;
    return 0;
}