Cod sursa(job #2448000)

Utilizator raduandreicaRadu Andreica raduandreica Data 15 august 2019 14:16:05
Problema Adapost 2 Scor 44
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.99 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 cautbin2(float x , float y , float dist , float sum);
punct cautbin1(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 cautbin2(x , y , dist/2 , sum);
    if(sumxlow == m)
        return cautbin2(xlow.x , xlow.y , dist/2 , sumxlow);
    if(sumylow == m)
        return cautbin2(ylow.x , ylow.y , dist/2 , sumylow);
    if(sumxhigh == m)
        return cautbin2(xhigh.x , xhigh.y , dist/2 , sumxhigh);
    if(sumyhigh == m)
        return cautbin2(yhigh.x , yhigh.y , dist/2 , sumyhigh);
}

punct cautbin2(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 cautbin1(x , y , dist , sum);
    if(sumxlow == m)
        return cautbin1(xlow.x , xlow.y , dist , sumxlow);
    if(sumylow == m)
        return cautbin1(ylow.x , ylow.y , dist , sumylow);
    if(sumxhigh == m)
        return cautbin1(xhigh.x , xhigh.y , dist , sumxhigh);
    if(sumyhigh == m)
        return cautbin1(yhigh.x , yhigh.y , dist , 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 = cautbin2(0 , 0 , 1000 , s);
    fout << ans.x << " " << ans.y;
    return 0;
}