Pagini recente » Cod sursa (job #1170983) | Cod sursa (job #2887988) | Cod sursa (job #970915) | Cod sursa (job #1386265) | Cod sursa (job #2066232)
#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 sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
long long dist(punct puncte[], int n, punct a) // suma distantelor de la punctul a la cele n puncte din plan
{
long long sum = 0;
for(int i = 1; i <= n; ++i) {
sum += dist_a_la_b(a, puncte[i]);
}
return sum;
}
long long minim_dist(double a, double b, double c, double d, int &direction)
{
if(a <= b and a <= c and a <= d) {
direction = 1;
return a;
}
if(b <= a and b <= c and b <= d) {
direction = 2;
return b;
}
if(c <= a and c <= b and c <= d) {
direction = 3;
return c;
}
if(d <= a and d <= b and d <= c) {
direction = 4;
return d;
}
}
int main()
{
int n;
fin >> n;
for(int i = 1; i <= n; ++i) {
double x, y;
fin >> x >> y;
puncte[i].x = x * 1000;
puncte[i].y = y * 1000;
}
punct centr_greutate;
long long sum_x = 0;
long long sum_y = 0;
for(int i = 1; i <= n; ++i) {
sum_x += puncte[i].x;
sum_y += puncte[i].y;
}
centr_greutate.x = sum_x / n;
centr_greutate.y = sum_y / n;
punct solutie;
solutie.x = centr_greutate.x;
solutie.y = centr_greutate.y;
int pas = 100;
while(pas != 1) {
long long dist1;
long long dist2;
long long dist3;
long long dist4;
punct Ox_dr = solutie;
punct Ox_st = solutie;
punct Oy_up = solutie;
punct Oy_dw = solutie;
Ox_dr.x = solutie.x + pas;
Ox_st.x = solutie.x - pas;
Oy_up.y = solutie.y + pas;
Oy_dw.y = solutie.y - pas;
dist1 = dist(puncte, n, Oy_up);
dist2 = dist(puncte, n, Ox_dr);
dist3 = dist(puncte, n, Oy_dw);
dist4 = dist(puncte, n, Ox_st);
minim_dist(dist1, dist2, dist3, dist4, direction);
if(direction == 1) {
solutie = Oy_up;
}
else if(direction == 2) {
solutie = Ox_dr;
}
else if(direction == 3) {
solutie = Oy_dw;
}
else {
solutie = Ox_st;
}
pas /= 2;
}
fout << solutie.x / 1000 << " " << solutie.y / 1000;
return 0;
}