Pagini recente » Cod sursa (job #768450) | Cod sursa (job #694610) | Cod sursa (job #911415) | Cod sursa (job #2603125) | Cod sursa (job #2070999)
#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;
}