Pagini recente » Cod sursa (job #896708) | Cod sursa (job #1630662) | Cod sursa (job #2859039) | Cod sursa (job #1081572) | Cod sursa (job #1846025)
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
const int Q=50007;
int n;
struct point
{
double x,y;
}v[Q];
std::map<double, map<double,double> > prec;
static double aux,dist_act,gx,gy,pas;
double dist(double a, double b)
{
double rez=0;
for(int i=1; i<=n; i++)
{
rez+=sqrt((a-v[i].x)*(a-v[i].x) + (b-v[i].y)*(b-v[i].y));
if(rez>dist_act)
return rez;
}
return rez;
}
bool inline bra1()
{
int sgn=rand()&1;
sgn*=2;
sgn--;
aux=dist(gx,gy+sgn*pas);
if(aux<dist_act)
{
gy+=sgn*pas;
dist_act=aux;
return 1;
}
else
{
aux=dist(gx,gy-sgn*pas);
if(aux<dist_act)
{
gy-=sgn*pas;
dist_act=aux;
return 1;
}
}
return 0;
}
bool inline bra2()
{
int sgn=rand()&1;
sgn*=2;
sgn--;
aux=dist(gx+pas*sgn,gy);
if(aux<dist_act)
{
gx+=pas*sgn;
dist_act=aux;
return 1;
}
else
{
aux=dist(gx-sgn*pas,gy);
if(aux<dist_act)
{
gx-=sgn*pas;
dist_act=aux;
return 1;
}
}
return 0;
}
int main()
{
freopen("adapost2.in","r",stdin);
freopen("adapost2.out","w",stdout);
cin>>n;
gx=0,gy=0;
for(int i=1; i<=n; i++)
{
cin>>v[i].x>>v[i].y;
gx+=v[i].x;
gy+=v[i].y;
}
gx/=n;
gy/=n;
pas=1<<9;
aux,dist_act=dist(gx,gy);
for(int tmp=1; tmp<=40; tmp++)
{
if(rand()&1)
{
if(bra1());
else if( bra2());
else pas/=2;
}
else
{
if (bra2());
else if( bra1());
else pas/=2;
}
if(pas<0.001)
break;
}
printf("%.6lf %.6lf\n",gx,gy);
return 0;
}