Pagini recente » Cod sursa (job #1754222) | Cod sursa (job #3160570) | Cod sursa (job #2049305) | Cod sursa (job #2942788) | Cod sursa (job #1815709)
#include <fstream>
#include <algorithm>
struct punct
{
double x,y;
};
int n;
punct adapost_final, adapost_curent, soldati[50001];
double best_distance;
double current_distance;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
double cost(punct p)
{
double cost = 0;
for (int i = 0; i < n; ++i)
cost += std::sqrt((soldati[i].x - p.x) * (soldati[i].x - p.x) + (soldati[i].y - p.y) * (soldati[i].y - p.y));
return cost;
}
int main()
{
std::ifstream fin("adapost2.in");
std::ofstream fout("adapost2.out");
fin>>n;
for (int i = 0; i < n; ++i)
{
fin>>soldati[i].x>>soldati[i].y;
adapost_final.x += soldati[i].x;
adapost_final.y += soldati[i].y;
}
adapost_final.x/=n;
adapost_final.y/=n;
best_distance = cost(adapost_final);
double pas = 500.0;
while (pas > 0.00001)
{
for (int i = 0; i < 4; ++i)
{
adapost_curent = {adapost_final.x + dx[i] * pas, adapost_final.y + dy[i] * pas};
current_distance = cost(adapost_curent);
if (current_distance < best_distance)
{
best_distance = current_distance;
adapost_final = adapost_curent;
}
}
pas /= 2.0;
}
fout << adapost_final.x << " " << adapost_final.y;
fout.close();
fin.close();
return 0;
}