Pagini recente » Cod sursa (job #1739542) | Cod sursa (job #1098835) | Cod sursa (job #2669512) | Cod sursa (job #865299) | Cod sursa (job #1838954)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
#define MAXITR 40 /* GASIT EXPERIMENTAL */
class Point {
public:
double x, y;
Point(){
}
Point(const double x, const double y) {
this->x = x;
this->y = y;
}
};
//ridicare la patrat
inline double sqr(double x) {
return x * x;
}
//functie ce returneaza distanta intre 2 puncte
inline double dist(Point A, Point B) {
return sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));
}
int N;
vector <Point> v;
//functie ce returneaza suma distantelor de la un punct la toate cele date
double distToAll(Point A) {
double sum = 0;
for (int i = 1; i <= N; ++i)
sum += dist(v[i], A);
return sum;
}
const int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }; //vector de directii
Point Bsearch(Point A) { //cautam punctul dorit
Point solPoint = A;
double solDist = distToAll(A);
double Step = 256.0; //pasul de modificare al punctului
for (int itr = 1; itr <= MAXITR; ++itr) {
double nextStep = Step * 0.5; //potentialul pas urmator
double x = solPoint.x;
double y = solPoint.y;
for (int i = 0; i < 4; ++i) { //incerc sa il duc in toate cele 4 directii
double xx = x + dir[i][0] * Step;
double yy = y + dir[i][1] * Step;
Point auxPoint = Point(xx, yy); //noul punct obtinut
double auxDist = distToAll(auxPoint); //ii calculez distanta totala
if (auxDist < solDist) { //daca e mai buna
solDist = auxDist; //actualizez distanta
solPoint = auxPoint; //actualizez punctul
nextStep = Step; //las acelasi pas, poate ajuta in continuare
}
}
Step = nextStep; //setez noul pas (sau ramane acelasi)
}
return solPoint; //rezultatul
}
int main() {
fin >> N;
v.resize(N + 2);
//citire
double x, y, medX = 0, medY = 0;
for (int i = 1; i <= N; ++i) {
fin >> x >> y;
v[i] = Point(x, y);
medX += x;
medY += y;
}
medX /= N;
medY /= N;
Point sol = Bsearch(Point(medX, medY)); //pornim de la centrul de greutate
//afisare
fout << fixed << setprecision(4);
fout << sol.x << " " << sol.y;
return 0;
}