Cod sursa(job #2070999)

Utilizator gundorfMoldovan George gundorf Data 20 noiembrie 2017 08:24:41
Problema Adapost 2 Scor 7
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <iostream>
#include <fstream>
#define Nmax 50002
#include <cmath>
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");

int n;
struct coordonate
{
    int x,y;
} v[Nmax],Cg; //Cg=centru de greutate
int dl[]={0,0,1,-1};
int dc[]={1,-1,0,0};
const int inf=9999999;
void Citire ()
{
    int i;
    float a,b;
    fin>>n;
    Cg.x=0;
    Cg.y=0;
    for (i=1;i<=n;i++)
    {
        fin>>a>>b;
        v[i].x=(int)(a*1000);
        v[i].y=(int)(b*1000);
        Cg.x+=v[i].x;
        Cg.y+=v[i].y;
    }
    Cg.x/=n;
    Cg.y/=n;

    /*for (i=1;i<=n;i++)
        fout<<v[i].x<<" "<<v[i].y<<"\n";*/
}
float Distanta (float a,float b)
{
    float distanta=0;
    int i;
    for (i=1;i<=n;i++)
        distanta+=(float)sqrt((v[i].x-a)*(float)(v[i].x-a)+(float)(v[i].y-b)*(float)(v[i].y-b));
    return distanta;
}



int main()
{ int pas=100;//pasul cu care ma misc ca sa mut pozitia
 int  referinta=1;//eroarea maxima permisa
    int i,ok=1;
    int ibun;//i-ul pentru care se obtine dmin (i-ul din forul pentru a stabili lv si cv)
    float dmin,dlucru;// distanta minima la un anumit pas, dintre vecini si distanta la care se aflu punctul de lucru de toate bazele
    int  lv,cv;//linie variabila, coloana variabila
 coordonate lucru; //cordonata de lucru, cu care ma tot mut pana gasesc pozitia minina

    Citire();

    lucru.x=Cg.x;
    lucru.y=Cg.y;
    dlucru=Distanta(lucru.x,lucru.y);
    while (ok!=0)
    {
        ok=0;
        dmin=inf;
        for (i=0;i<4;i++) // calculez distanele la care se afla vecinii punctului de lucru, miscandu-ma cu pasi de marime=*pas*
        {
            lv=lucru.x+dl[i]*pas;
            cv=lucru.y+dc[i]*pas;
            float z=Distanta(lv,cv);// distanta de la lv si cv la toate bazele
            if (z<dlucru&&z<dmin) {dmin=z;ibun=i;ok=1;} //daca distanta e mai mica decat dlucru si e si minima dintre ceilalti vecini, aleg varianta asta
        }
        if (ok==1) // daca se poate continua folosind acelasi pas, actulizez doar punctul de lucru si dlucru
        { lucru.x=lucru.x+pas*dl[ibun];
            lucru.y=lucru.y+pas*dc[ibun];
            dlucru=dmin;
        }
        else if (ok==0&&pas-referinta>0) // daca nu, si pasul e indeajuns de mare incat sa poate fi micsorat, micosrez pasul si reiau smecheria
        {
            pas/=2;
            ok=1;
        }
    }

 fout<<(float)lucru.x/1000<<" "<<(float)lucru.y/1000;


//fout<<Distanta(4144,4289);
    return 0;
}