Pagini recente » Cod sursa (job #1821246) | Cod sursa (job #703031) | Cod sursa (job #2574814) | Cod sursa (job #918680) | Cod sursa (job #528680)
Cod sursa(job #528680)
// infoarena: problema/adapost2 //
#include <fstream>
#include <cmath>
#include <vector>
using namespace std;
ifstream in("adapost2.in");
ofstream out("adapost2.out");
const int MAXN = 50010;
const double err = 0.0000001;
int n,m,i,j;
template<typename T>
struct point
{
T x,y;
point(){}
point(T _x, T _y)
{
x = _x;
y = _y;
}
T distance(point<T> other)
{
return sqrt((x-other.x)*(x-other.x) + (y-other.y)*(y-other.y));
}
T distance_sum(vector<point<T> > a)
{
T r=0;
typeof(a.begin()) it, end = a.end();
for(it=a.begin(); it!=end; it++)
r += distance(*it);
return r;
}
};
vector<point<double> > v;
point<double> r, tmp;
double sx, sy, pace, s1, s2, s3, s4, s, sc;
int main()
{
in>>n;
for(i=0; i<n; i++)
{
in>>tmp.x>>tmp.y;
v.push_back(tmp);
sx += tmp.x;
sy += tmp.y;
}
r = point<double>(sx/n, sy/n);
s = r.distance_sum(v);
pace = 100;
while(pace > err)
{
s1 = point<double>(r.x-pace, r.y).distance_sum(v);
s2 = point<double>(r.x+pace, r.y).distance_sum(v);
s3 = point<double>(r.x, r.y-pace).distance_sum(v);
s4 = point<double>(r.x, r.y+pace).distance_sum(v);
sc = min(min(s1,s2), min(s3,s4));
if(s < sc)
{
pace /= 2;
continue;
}
if(s1 == sc)
r.x -= pace;
else if(s2 == sc)
r.x += pace;
else if(s3 == sc)
r.y -= pace;
else if(s4 == sc)
r.y += pace;
s = sc;
}
//out<<r.distance_sum(v)<<'\n'<<point<double>(4.1442, 4.2898).distance_sum(v)<<"\n\n";
out<<r.x<<' '<<r.y;
return 0;
}