Pagini recente » Cod sursa (job #1907532) | Cod sursa (job #1572799) | Cod sursa (job #2205845) | Istoria paginii runda/leitentw1/clasament | Cod sursa (job #1062089)
#include<fstream>
#include<cmath>
using namespace std;
const int NMAX = 50005;
int i,j,N; int Dx[]={-1,0,0,1}; int Dy[]={0,-1,1,0};
double L,SolX,SolY,Best,X[NMAX],Y[NMAX],NewX,NewY,Cost;
double Dist(double A,double B,double C,double D)
{
return sqrt((A-C)*(A-C)+(B-D)*(B-D));
}
int main()
{
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
fin>>N;
for(i=1;i<=N;i++)
{
fin>>X[i]>>Y[i];
SolX+=X[i]; SolY+=Y[i];
}
SolX/=N; SolY/=N;
for(i=1;i<=N;i++) Best+=Dist(X[i],Y[i],SolX,SolY);
for(L=100;L>0.0001;L/=2)
for(i=0;i<4;i++)
{
NewX=SolX+L*Dx[i]; NewY=SolY+L*Dy[i]; Cost=0;
for(j=1;j<=N;j++) Cost+=Dist(X[j],Y[j],NewX,NewY);
if(Cost<Best)
{
Best=Cost; SolX=NewX; SolY=NewY;
L*=2; break;
}
}
fout<<SolX<<" "<<SolY<<'\n';
fin.close(); fout.close();
return 0;
}