Cod sursa(job #1072530)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 4 ianuarie 2014 16:20:37
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#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, 0, -1};
double dy[] = {1, 0, -1, 0};


//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.00001)
	{
		bool improve = false;

		for(int i = 0; i < 4; 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
}