记录编号	378346	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	最小距离和	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	22.358 s
提交时间	2017-03-03 19:26:10	内存使用	1.84 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;
const double EPS = 1e-5;
const double PI = acos(-1);
const int MAXN = 1e5 + 10;
const double INF = 1e100;

struct Node {
	double x, y;
	Node() {}
	Node(double x_, double y_) { x = x_, y = y_; }
} ns[MAXN];

struct Line {
	double a, b, c;
	Line() {}
	Line(double alpha, double b_) {
		alpha -= PI * (int)(alpha / PI);
		if (fabs(alpha - PI / 2) <= 1e-6) a = INF;
		else if (fabs(alpha + PI / 2) <= 1e-6) a = -INF;
		else a = tan(alpha);
		 b = -1, c = b_;
	}
	Line(Node a_, Node b_) {
		if (b_.x - a_.x == 0) a = -INF;
		else a = -((b_.y - a_.y) / (b_.x - a_.x));
		b = 1;
		c = a_.y + a_.x * a;
	}
};

int n;
double avay, avak;
double sumx, sumy;

inline void init() {
	for (int i = 1; i <= n; i++) sumx += ns[i].x, sumy += ns[i].y;
	avay = sumy / n;
}

inline double cal_all(Line a) {
	double res = 0;
	for (int i = 1; i <= n; i++)
		res += fabs(a.a * ns[i].x + a.b * ns[i].y - a.c) / sqrt(a.a * a.a + a.b * a.b);
	return res; 
}

inline void read() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lf %lf", &ns[i].x, &ns[i].y);
}

inline double cal_ne_b(double alpha, double now_pos, double &ne_pos, double T) {
	double ans = INF;
	double b;
	for (int i = 1; i <= 4; i++) {
		b = now_pos + (double)(rand() & 1 ? 1 : -1) * (double)(rand() % 1000 + 1) * T / 1000.0;
		double tmp = cal_all(Line(alpha, b));
		
		if (tmp < ans) ans = tmp, ne_pos = b;
	}
	return ans;
}

inline double solve_b(double alpha) {
	int cant_times;
	double T = 1e5, step = 0.6;
	double now_pos = 0, now_ans = 0, ans = 0;
	ans = now_ans = cal_all(Line(alpha, now_pos));
	
	while (T >= 1e-4) {
		double tmp;
		double now_dis = cal_ne_b(alpha, now_pos, tmp, T);
		double dE = now_ans - now_dis;
		
        if (now_dis < ans) ans = now_dis;
         
        if (dE >= 0) now_ans = now_dis, now_pos = tmp, cant_times = 0;
        else {
            cant_times++;
            if (exp(dE / T) >= (double)(rand() % 1000 + 1) / 1000.0) now_ans = now_dis, now_pos = tmp;
        }
		T *= step;
	}
	return ans;
}

inline double cal_ne_alpha(double now_pos, double &ne_pos, double T) {
	double ans = INF;
	double alpha;
	for (int i = 1; i <= 2; i++) {
		alpha = now_pos + (double)(rand() & 1 ? 1 : -1) * (double)(rand() % 1000 + 1) * T / 1000.0;
		double tmp = solve_b(alpha);
		
		if (tmp < ans) ans = tmp, ne_pos = alpha;
	}
	return ans;
}

inline void solve() {
	init();
	int cant_times;
	int times = 0;
	double T = PI, step = 0.9;
	double now_pos = 0, now_ans = 0, ans = 0;
	ans = now_ans = solve_b(now_pos);
	double ans_tar;
	
	while (T >= 1e-6) {
		times++;
		double tmp;
		double now_dis = cal_ne_alpha(now_pos, tmp, T);
		double dE = now_ans - now_dis;
		
		if (now_dis < ans) ans = now_dis, ans_tar = now_pos;
		
        if (dE >= 0) now_ans = now_dis, now_pos = tmp, cant_times = 0;
        else {
            cant_times++;
            if (exp(dE / T) >= (double)(rand() % 1000 + 1) / 1000.0) now_ans = now_dis, now_pos = tmp;
        }
        
        T *= step;
	}
	printf("%.2lf\n", ans);
}

inline void violence() {
	double ans = INF;
	int ansi, ansj;
	Line tmp;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			tmp = Line(ns[i], ns[j]);
			double now_dis = cal_all(tmp);
			if (now_dis < ans) ans = now_dis, ansi = i, ansj = j;
		}
	}
	
	tmp = Line(ns[1], ns[n]);
	double now_dis = cal_all(tmp);
	
	printf("%.2lf\n", ans, ansi, ansj);
}

int main() {
#ifdef LOCAL
	freopen("test.in", "r", stdin);
#endif
#ifndef BAT
	freopen("space.in", "r", stdin);
	freopen("space.out", "w", stdout);
#endif
	srand((unsigned)19970830);
	read();
	if (n >= 1000) solve();
	else violence();
	return 0;
}