Pagini recente » Cod sursa (job #1582926) | Cod sursa (job #3281578) | Cod sursa (job #875646) | Cod sursa (job #2222153) | Cod sursa (job #2067156)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream in("adapost2.in");
ofstream out("adapost2.out");
#define ll long long
#define ull unsigned long long
#define pb push_back
const int NMax = 5e4 + 5;
const int sqMax = 320 + 5;
// ideea de rezolvare se bazeaza pe presupunerea ca
// exista un singur punct de minim cerut, iar
// toate celelalte puncte converg doar catre acesta;
int N;
typedef pair<double,double> point;
point p[NMax];
// p[i] - al i-lea punct din input;
double getDist(point a,point b);
// getDist(a,b) return-eaza distanta euclidiana dintre cele doua puncte;
double getSum(point x);
// getSum(x) return-eaza suma distantelor de la fiecare punct din cele date la punctul x;
point solve();
// return-eaza un punct solutie;
int main() {
in>>N;
for (int i=1;i <= N;++i) {
in>>p[i].first>>p[i].second;
}
point adapost = solve();
out<<fixed<<setprecision(4)<<adapost.first<<' '<<adapost.second;
in.close();out.close();
return 0;
}
point solve() {
point adapost = point(0,0);
// se initializeaza punctul raspuns cu centrul de greutate;
for (int i=1;i <= N;++i) {
adapost.first += p[i].first;
adapost.second += p[i].second;
}
adapost.first /= N;
adapost.second /= N;
double add = 100;
// se cauta cel mai bun punct prin mutari stanga,dreapta,sus,jos de lungime add;
while (add > 1e-3) {
// cat timp se poate ajunge inca la un punct mai bun folosind distanta add,
// se face acest lucru;
while (true) {
point pTop = point(adapost.first,adapost.second + add);
point pBot = point(adapost.first,adapost.second - add);
point pLeft = point(adapost.first - add,adapost.second);
point pRight = point(adapost.first + add,adapost.second);
double sumTop = getSum(pTop), sumBot = getSum(pBot),
sumLeft = getSum(pLeft), sumRight = getSum(pRight);
double mn = min(min(sumTop,sumBot),min(sumLeft,sumRight));
point minPoint;
if (mn == sumTop) {
minPoint = pTop;
}
else if (mn == sumBot) {
minPoint = pBot;
}
else if (mn == sumLeft) {
minPoint = pLeft;
}
else {
minPoint = pRight;
}
// daca punctul la care ne aflam este mai optim decat cei 4 "vecini",
// atunci trebuie micsorata distanta add de cautare;
if (mn >= getSum(adapost)) {
break;
}
else {
adapost = minPoint;
}
}
add /= 2;
}
return adapost;
}
double getSum(point a) {
double ret = 0;
for (int i=1;i <= N;++i) {
ret += getDist(a,p[i]);
}
return ret;
}
double getDist(point a,point b) {
double val = (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
return sqrt(val);
}