Pagini recente » Cod sursa (job #2382910) | Cod sursa (job #950022) | Cod sursa (job #2644321) | Cod sursa (job #1783236) | Cod sursa (job #528586)
Cod sursa(job #528586)
// infoarena: problema/adapost2 //
#include <fstream>
#include <cmath>
using namespace std;
ifstream in("adapost2.in");
ofstream out("adapost2.out");
const int MAXN = 50000;
const double eps = 0.00000001;
struct point {
double x,y;
point(){}
point(double _x, double _y)
{
x = _x;
y = _y;
}
};
point p[MAXN],r;
double err, s, sc,s1,s2,s3,s4,sx,sy,pace,steps;
int i,n;
inline double dist(point a, point b)
{
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
inline double suma_dist(point a)
{
double r=0;
for(i=1; i<=n; i++)
r+=dist(a, p[i]);
return r;
}
int main()
{
in>>n;
in>>p[1].x>>p[1].y;
for(i=2; i<=n; i++)
{
in>>p[i].x>>p[i].y;
sx += p[i].x;
sy += p[i].y;
}
r = point(sx/n, sy/n);
pace = 100;
s = suma_dist(r);
while(pace > eps)
{
s1 = suma_dist(point(r.x-pace, r.y)); // left
s2 = suma_dist(point(r.x+pace, r.y)); // right
s3 = suma_dist(point(r.x, r.y-pace)); // up
s4 = suma_dist(point(r.x, r.y+pace)); // down
sc = min(min(s1,s2),min(s3,s4));
if(s-sc < eps)
{
pace /= 733;
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<<'\n'<<suma_dist(r)<<'\n'<<suma_dist(point(4.1442, 4.2898))<<"\n\n";
out<<r.x<<' '<<r.y;
return 0;
}