- #include#include#include using namespace std;
- inline int read() {
- int x,
- f = 1;
- char c;
- while ((c = getchar()) < '0' || c > '9') if (c == ' - ') f = -1;
- for (x = c - '0'; (c = getchar()) >= '0' && c <= '9';) x = (x << 3) + (x << 1) + c - '0';
- return x * f;
- }#define MN 200000 double ans = 1e18;
- struct P {
- int x,
- y;
- }
- p[MN + 5],
- t[MN + 5];
- bool cmpx(P a, P b) {
- return a.x < b.x;
- }
- bool cmpy(P a, P b) {
- return a.y < b.y;
- }
- double sqr(double x) {
- return x * x;
- }
- double len(P a, P b) {
- return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
- }
- void solve(int l, int r) {
- if (r - l < 2) return;
- int m = l + r >> 1,
- i,
- j,
- k,
- cnt = 0;
- solve(l, m);
- solve(m + 1, r);
- for (i = l; i <= r; ++i) if (fabs(p[i].x - p[m].x) 2) t[++cnt] = p[i];
- sort(t + 1, t + cnt + 1, cmpy);
- for (i = 1; i <= cnt; ++i) for (j = i + 1; j <= cnt && t[j].y - t[i].y2; ++j) for (k = j + 1; k <= cnt && t[k].y - t[i].y2; ++k) ans = min(ans, len(t[i], t[j]) + len(t[j], t[k]) + len(t[k], t[i]));
- }
- int main() {
- int n = read(),
- i;
- for (i = 1; i <= n; ++i) p[i].x = read(),
- p[i].y = read();
- sort(p + 1, p + n + 1, cmpx);
- solve(1, n);
- printf("%.6lf", ans);
- }
来源: http://www.bubuko.com/infodetail-1982441.html