Pagini recente » Cod sursa (job #2041862) | Cod sursa (job #2265237) | Cod sursa (job #2075285) | Cod sursa (job #2532250) | Cod sursa (job #528504)
Cod sursa(job #528504)
// 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;
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 = (maxx+maxy-minx-miny)/1000;
err = 1<<29;
s = suma_dist(r);
while(err > 0.00001)
{
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(s1 == sc)
{
// left
r.x -= pace;
err = abs(s - sc);
}
if(s2 == sc)
{
// right
r.x += pace;
err = abs(s - sc);
}
if(s3 == sc)
{
// up
r.y -= pace;
err = abs(s - sc);
}
if(s4 == sc)
{
// down
r.y += pace;
err = abs(s - sc);
}
s = sc;
}
out<<s<<'\n'<<suma_dist(point(4.1442, 4.2898))<<"\n\n";
out<<r.x<<' '<<r.y;
return 0;
}