Pagini recente » Cod sursa (job #32603) | Cod sursa (job #38230) | Cod sursa (job #2931859) | Cod sursa (job #2999509) | Cod sursa (job #2303035)
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
const int NMAX=50000;
const double eps=0.001;
struct point
{
double x, y;
};
point adapost, nadapost;
point v[NMAX+5];
int dx[4]={0, 1, 0, -1};
int dy[4]={1, 0, -1, 0};
int n;
double dist(point p1, point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double dist_tot(point a)
{
double suma=0;
for(int i=1;i<=n;i++)
suma=suma+dist(a, v[i]);
return suma;
}
int main()
{
int i;
bool ok=0;
double distanta_minima, distanta, pas=1000;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
adapost.x=adapost.x+v[i].x;
adapost.y=adapost.y+v[i].y;
}
adapost.x=adapost.x/n;
adapost.y=adapost.y/n;
//adapost trebuie sa fie initializat cu un pct din interior, asa ca pt a fi sigur de acest lucru, l-am initializat cu coordonatele elementului median
distanta_minima=dist_tot(adapost);
while(pas>eps)
{
ok=1;
for(i=0;i<4;i++)
{
nadapost.x=adapost.x+pas*dx[i];
nadapost.y=adapost.y+pas*dy[i];
distanta=dist_tot(nadapost);
if(distanta<distanta_minima)
{
distanta_minima=distanta;
adapost.x=nadapost.x;
adapost.y=nadapost.y;
ok=0;
break;
}
}
if(ok==1)
pas=pas*0.5;
}
fout<<adapost.x<<" "<<adapost.y<<"\n";
return 0;
}