Pagini recente » Cod sursa (job #2384567) | Cod sursa (job #1369219) | Cod sursa (job #1371498) | Cod sursa (job #2630217) | Cod sursa (job #1072526)
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iterator>
#include <assert.h>
using namespace std;
const string file = "adapost2";
const string infile = file + ".in";
const string outfile = file + ".out";
const int INF = 0x3f3f3f3f;
struct Point2D
{
double x;
double y;
};
double dx[] = {0, 1, 1 ,1 ,0, -1, -1, -1};
double dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
double distance2D(Point2D& a, Point2D& b)
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
double computeDist(Point2D& center, vector<Point2D>& points)
{
double dist = 0;
for(unsigned int i = 0; i < points.size(); i++)
{
dist += distance2D(center, points[i]);
}
return dist;
}
int main()
{
#ifdef ONLINE_JUDGE
ostream &fout = cout;
istream &fin = cin;
#else
fstream fout(outfile.c_str(), ios::out);
fstream fin(infile.c_str(), ios::in);
#endif
int N;
fin >> N;
vector<Point2D> points(N);
Point2D center;
center.x = 0;
center.y = 0;
for(int i = 0; i < N; i++)
{
fin >> points[i].x >> points[i].y;
center.x += points[i].x;
center.y += points[i].y;
}
center.x /= N;
center.y /= N;
double cDistance = computeDist(center, points);
double c = 1000;
while(c > 0.0001)
{
bool improve = false;
for(int i = 0; i < 8; i++)
{
Point2D newCenter;
newCenter.x = center.x + c * dx[i];
newCenter.y = center.y + c * dy[i];
double newDist = computeDist(newCenter, points);
if(newDist < cDistance)
{
center = newCenter;
cDistance = newDist;
improve = true;
break;
}
}
if(improve == false)
{
c /= 10;
}
}
fout << setprecision(4) << fixed << center.x << " " << center.y << "\n";
#ifdef ONLINE_JUDGE
#else
fin.close();
fout.close();
#endif
}