BZOJ 2458 最小三角形

题面

一个平面上有很多点，求他们中的点组成的周长最小的三角形的周长。

题解

跟平面最近点对差不多，也是先把区间内的点按x坐标从中间分开，递归处理，然后再处理横跨中线的三角形。

如何缩小范围？设左右两个子区间发现的最小周长是d，则与中线距离超过d / 2都没有用了，对于一个点，所有与它距离超过d / 2的点也都没有用。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long ll;

template <class T>

void read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

	if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

	x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 200005;

int n;

struct point {

    double x, y;

    bool operator < (const point &b) const{

	return x < b.x;

    }

    point operator - (const point &b){

	return (point){x - b.x, y - b.y};

    }

    double norm(){

	return sqrt(x * x + y * y);

    }

} p[N], a[N], b[N], c[N];

double calc(point x, point y, point z){

    return (x - y).norm() + (y - z).norm() + (z - x).norm();

}

double solve(int l, int r){

    if(l == r) return 1e20;

    int mid = (l + r) >> 1;

    double xmid = (p[mid].x + p[mid + 1].x) / 2;

    double d = min(solve(l, mid), solve(mid + 1, r));

    int pos = l, pb = 0, pc = 0, pl = l, pr = mid + 1;

    while(pos <= r)

	if(pl <= mid && (pr > r || p[pl].y < p[pr].y)){

	    if(p[pl].x > xmid - d / 2) b[++pb] = p[pl];

	    a[pos++] = p[pl++];

	}

	else{

	    if(p[pr].x < xmid + d / 2) c[++pc] = p[pr];

	    a[pos++] = p[pr++];

	}

    for(int i = l; i <= r; i++)

	p[i] = a[i];

    if(l + 1 == r) return 1e20;

    for(int i = 1, j = 1; i <= pb; i++){

	while(j <= pc && b[i].y - c[j].y > d / 2) j++;

	for(int k = j; k <= pc && abs(b[i].y - c[k].y) < d / 2; k++)

	    for(int h = k + 1; h <= pc && abs(b[i].y - c[h].y) < d / 2; h++)

		d = min(d, calc(b[i], c[k], c[h]));

    }

    for(int i = 1, j = 1; i <= pc; i++){

	while(j <= pb && c[i].y - b[j].y > d / 2) j++;

	for(int k = j; k <= pb && abs(c[i].y - b[k].y) < d / 2; k++)

	    for(int h = k + 1; h <= pb && abs(c[i].y - b[h].y) < d / 2; h++)

		d = min(d, calc(c[i], b[k], b[h]));

    }

    return d;

}

int main(){

    read(n);

    for(int i = 1; i <= n; i++)

	scanf("%lf%lf", &p[i].x, &p[i].y);

    sort(p + 1, p + n + 1);

    printf("%.6lf\n", solve(1, n));

    return 0;

}