Cod sursa(job #2071001)

Utilizator gundorfMoldovan George gundorf Data 20 noiembrie 2017 08:29:07
Problema Adapost 2 Scor 26
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 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
{
    float 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=a;
        v[i].y=b;
        Cg.x+=a;
        Cg.y+=b;
    }
    Cg.x/=(float)n;
    Cg.y/=(float)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)*(v[i].x-a)+(v[i].y-b)*(v[i].y-b));
    return distanta;
}



int main()
{ float pas=1000;//pasul cu care ma misc ca sa mut pozitia
 float referinta=0.001;//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
    float 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++)
        {
            lv=(float)lucru.x+dl[i]*pas;
            cv=(float)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;}
        }
        if (ok==1)
        { lucru.x=lucru.x+pas*dl[ibun];
            lucru.y=lucru.y+pas*dc[ibun];
            dlucru=dmin;
        }
        else if (ok==0&&pas-referinta>=0)
        {
            pas/=2;
            ok=1;
        }
    }

 fout<<lucru.x<<" "<<lucru.y;



    return 0;
}