Pagini recente » Cod sursa (job #2482577) | Cod sursa (job #1299185) | Cod sursa (job #2465989) | Cod sursa (job #3174088) | Cod sursa (job #2066412)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
const int Nmax = 5e4 + 10;
int direction;
struct punct {
double x;
double y;
}puncte[Nmax];
double dist_a_la_b(punct a, punct b) // distanta dintre 2 puncte in plan
{
return (double)sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double dist(punct puncte[], int n, punct a) // suma distantelor de la punctul a la cele n puncte din plan
{
double sum = 0;
for(int i = 1; i <= n; ++i) {
sum += dist_a_la_b(a, puncte[i]);
}
return sum;
}
int main()
{
int n;
fin >> n;
double sum_x = 0.0;
double sum_y = 0.0;
for(int i = 1; i <= n; ++i) {
double x, y;
fin >> x >> y;
puncte[i].x = x * 1000;
puncte[i].y = y * 1000;
sum_x += puncte[i].x;
sum_y += puncte[i].y;
}
punct solutie;
solutie.x = sum_x / n;
solutie.y = sum_y / n;
double pas = 100;
while(pas > 1) {
double dist0;
double dist1;
double dist2;
double dist3;
double dist4;
punct Ox_dr = solutie;
punct Ox_st = solutie;
punct Oy_up = solutie;
punct Oy_dw = solutie;
//intializam punctele din cele 4 directii cu semnificatia : Ox_dr -> punctul de pe axa Ox translatat la dreapta cu un pas
Ox_dr.x = solutie.x + pas;
Ox_st.x = solutie.x - pas;
Oy_up.y = solutie.y + pas;
Oy_dw.y = solutie.y - pas;
//calculam suma distantelor de la cele 5 puncte cheie la cele n puncte date din plan
dist0 = dist(puncte, n, solutie);
dist1 = dist(puncte, n, Oy_up);
dist2 = dist(puncte, n, Ox_dr);
dist3 = dist(puncte, n, Oy_dw);
dist4 = dist(puncte, n, Ox_st);
//daca inca exista un punct pentru care distanta sa fie mai mica atunci ne mutam in acel punct si continuam cautarea cu acel pas
if(dist0 > dist1) {
solutie = Oy_up;
continue;
}
if(dist0 > dist2) {
solutie = Ox_dr;
continue;
}
if(dist0 > dist3) {
solutie = Oy_dw;
continue;
}
if(dist0 > dist4) {
solutie = Ox_st;
continue;
}
pas *= 0.6; // am ajuns intr-un punct pentru care suma distantelor este minima si continuam cautarea injumatatind pasul
}
fout << fixed << setprecision(4) << solutie.x / 1000 << " " << solutie.y / 1000;
return 0;
}