Pagini recente » Cod sursa (job #2976482) | Cod sursa (job #1949784) | Cod sursa (job #155142) | Cod sursa (job #1638014) | Cod sursa (job #2083125)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream f("adapost2.in");
ofstream g("adapost2.out");
#define ll long long
#define ull unsigned long long
#define pb push_back
const int NMax = 5e4 + 5;
const int sqMax = 320 + 5;
int N;
typedef pair<double,double> punct;
punct p[50005];
double distanta(punct a,punct b)
{
return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
double suma(punct a)
{
double ret = 0;
for (int i=1; i <= N; ++i)
{
ret += distanta(a,p[i]);
}
return ret;
}
punct solve()
{
int i; punct adapost;
adapost.first = p[1].first;
adapost.second = p[1].second;
for ( i=2; i <= N; ++i)
{
adapost.first += p[i].first;
adapost.second += p[i].second;
}
adapost.first /= N;
adapost.second /= N;
double add = 100;
while (add > 0.0001)
{
// pana ajungem la un punct apropiat , tot micim distanta cu add
// CAUTAM punctul sus , jos , stanga , dreapta , si comparam cu cel din mijloc
//alegem punctul cel mai "bun"
punct sus,jos,stanga,dreapta;
sus.first = adapost.first;sus.second=adapost.second + add;
jos.first = adapost.first;jos.second=adapost.second - add;
stanga.first = adapost.first - add;stanga.first=adapost.first;
dreapta.first = adapost.first + add;dreapta.first =adapost.first;
double sumsus = suma(sus), sumjos= suma(jos), sumstanga = suma(stanga), sumdreapta = suma(dreapta);
double mn = min(min(sumsus,sumjos),min(sumstanga,sumdreapta));
punct minpunct;
if (mn == sumsus)
{
minpunct = sus;
}
else if (mn == sumjos)
{
minpunct = jos;
}
else if (mn == sumstanga)
{
minpunct = stanga;
}
else
{
minpunct = dreapta;
}
if (mn >= suma(adapost))
{
break;
}
else
{
adapost = minpunct;
}
add /= 2;
}
return adapost;
}
int main()
{
f>>N;
for (int i=1; i <= N; ++i)
{
f>>p[i].first>>p[i].second;
}
punct adapost;
adapost = solve();
g<<fixed<<setprecision(4)<<adapost.first<<' '<<adapost.second;
return 0;
}