Pagini recente » Cod sursa (job #374677) | Cod sursa (job #1031246) | Cod sursa (job #2600985) | Cod sursa (job #702002) | Cod sursa (job #528532)
Cod sursa(job #528532)
// 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], ds, ss, dj, sj,r,m;
float maxx, minx, maxy, miny, err, s, sc,s1,s2,s3,s4,sx,sy,pace,delta,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;
maxx = minx = p[1].x;
maxy = miny = p[1].y;
for(i=2; i<=n; i++)
{
in>>p[i].x>>p[i].y;
maxx = max(maxx, p[i].x);
minx = min(minx, p[i].x);
maxy = max(maxy, p[i].y);
miny = min(miny, p[i].y);
sx += p[i].x;
sy += p[i].y;
}
r = point(sx/n, sy/n);
pace = 10000;
err = 1<<29;
s = suma_dist(r);
delta = 0;
while(pace > 0.0001 && err > 0.0001)
{
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)
{
pace /= 3;
continue;
}
if(s1 == sc)
{
// left
r.x -= pace;
err = s - sc;
}
if(s2 == sc)
{
// right
r.x += pace;
err = s - sc;
}
if(s3 == sc)
{
// up
r.y -= pace;
err = s - sc;
}
if(s4 == sc)
{
// down
r.y += pace;
err = s - sc;
}
s = sc;
}
out<<suma_dist(r)<<'\n'<<suma_dist(point(4.1442, 4.2898))<<"\n\n";
out<<r.x<<' '<<r.y;
return 0;
}