Pagini recente » Cod sursa (job #1518622) | Cod sursa (job #2983219) | Cod sursa (job #2355875) | Cod sursa (job #1528363) | Cod sursa (job #1071057)
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<fstream>
#include<iomanip>
#define x first
#define y second
using namespace std;
const int MAX_N = 50000 + 5;
const double MAX_PAS = 16.0;
const double EPS_PAS = 0.0001;
const double EPS = 0.0000000001;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int n;
pair<double,double> points[MAX_N];
class MyReadingClass {
public:
MyReadingClass() {}
MyReadingClass(const char* string) {
file = fopen(string, "r");
max_buffer_size=1<<16;cursor=0;
fread(buffer, max_buffer_size, 1, file);
}
inline void operator>>(int &n) {
while('0' > buffer[cursor] || buffer[cursor] > '9') {
++cursor;
if(cursor == max_buffer_size) {
cursor = 0;
fread(buffer, max_buffer_size, 1, file);
}
}
n = 0;
while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
n = n * 10 + buffer[cursor] - '0';
++cursor;
if(cursor == max_buffer_size) {
cursor = 0;
fread(buffer, max_buffer_size, 1, file);
}
}
}
inline void operator>>(double &n) {
int integer_part;
double fractionary_part = 0.0,power_of_10 = 1.0;
(*this) >> integer_part;
n = integer_part;
if(buffer[cursor] != '.') return;
++cursor;
while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
power_of_10 /= 10.0;
fractionary_part += power_of_10 * static_cast<double>(buffer[cursor]-'0');
++cursor;
if(cursor == max_buffer_size) {
cursor = 0;
fread(buffer, max_buffer_size, 1, file);
}
}
n += fractionary_part;
}
private:
FILE *file;
char buffer[1<<16];
int max_buffer_size,cursor;
};
double cost(const pair<double,double> &point) {
double answer=0.0;
for(int i = 1; i <= n; ++i) {
answer += sqrt((point.x - points[i].x) * (point.x - points[i].x) + (point.y - points[i].y) * (point.y - points[i].y));
}
return answer;
}
int main() {
MyReadingClass fin("adapost2.in");
ofstream fout("adapost2.out");
pair<double,double> answer(0,0),next_answer;
fin >> n;
for(int i = 1; i <= n; ++i) {
fin >> points[i].x;
fin >> points[i].y;
answer.x += points[i].x;
answer.y += points[i].y;
}
answer.x /= n;
answer.y /= n;
double best_cost = cost(answer), current_cost;
for(double pas = MAX_PAS; pas >= EPS_PAS; pas /= 2.0) {
bool increase_pas=false;
for(int d = 0; d < 4; ++d) {
next_answer.x = answer.x + pas * dx[d];
next_answer.y = answer.y + pas * dy[d];
current_cost = cost(next_answer);
if(best_cost - current_cost >= EPS) {
best_cost = current_cost;
answer = next_answer;
increase_pas = true;
break;
}
}
if(increase_pas) {
pas *= 2.0;
}
}
fout << answer.x << " " << answer.y << endl;
return 0;
}