Pagini recente » Cod sursa (job #1282148) | Cod sursa (job #2039940) | Cod sursa (job #1710372) | Cod sursa (job #1900690) | Cod sursa (job #528564)
Cod sursa(job #528564)
// infoarena: problema/adapost2 //
#include <fstream>
#include <cmath>
using namespace std;
ifstream in("adapost2.in");
ofstream out("adapost2.out");
const int MAXN = 50000;
struct point {
float x,y;
point(){}
point(float _x, float _y)
{
x = _x;
y = _y;
}
};
point p[MAXN],r;
float err, s, sc,s1,s2,s3,s4,sx,sy,pace,steps;
int i,n;
inline float dist(point a, point b)
{
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
inline float suma_dist(point a)
{
float 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;
err = 1<<29;
s = suma_dist(r);
while(err > 0.000001 && ++steps < 100000)
{
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(sc > s || s - sc < 0.00001)
{
pace /= 2;
continue;
}
//out<<sc<<' ';
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;
err = s - sc;
s = sc;
}
//out<<'\n'<<suma_dist(r)<<'\n'<<suma_dist(point(4.1442, 4.2898))<<"\n\n";
out<<r.x<<' '<<r.y;
return 0;
}