Pagini recente » Cod sursa (job #1216286) | Cod sursa (job #851286) | Cod sursa (job #1842904) | Cod sursa (job #938357) | Cod sursa (job #528489)
Cod sursa(job #528489)
// 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;
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);
}
ss = point(minx, miny);
ds = point(maxx, miny);
sj = point(minx, maxy);
dj = point(maxx, maxy);
s = 1<<29;
err = 1<<29;
while(err > 0.0000001)
{
m = point((ss.x+ds.x)/2, (ss.y+sj.y)/2);
s1 = suma_dist(ss);
s2 = suma_dist(ds);
s3 = suma_dist(sj);
s4 = suma_dist(dj);
sc = min(min(s1,s2),min(s3,s4));
if(sc == s1)
{
// stanga sus
ds.x = m.x;
sj.y = m.y;
dj = m;
r = ss;
}
else if(sc == s2)
{
// dreapta sus
ss.x = m.x;
dj.y = m.y;
sj = m;
r = ds;
}
else if(sc == s3)
{
// stanga jos
ss.y = m.y;
dj.x = m.x;
ds = m;
r = sj;
}
else if(sc == s4)
{
// dreapta jos
sj.x = m.x;
ds.y = m.y;
ss = m;
r = dj;
}
err = abs(sc - s);
s = sc;
}
//out<<suma_dist(point(r.x, r.y))<<endl;
//out<<suma_dist(point(4.1442,4.2898))<<endl<<endl;
out<<r.x<<' '<<r.y;
return 0;
}