题目链接:bzoj2458: [BeiJing2011]最小三角形
学习推荐博客:分治法编程问题之最接近点对问题的算法分析
题解:先将所有点按x值排列,然后每次将当前区间[l,r]分成左右两半递归求解周长最小三角形。考虑到两半区间之间可能有连成最小三角形的情况,设dd为两半区间中最小三角形周长的最小值,筛选满足要求的点(x值与中点坐标x值的距离小于dd),然后按y值排序,进而暴搜出周长最小三角形。
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std; typedef long long ll;
const double inf = 0x3f3f3f3f;
const int N = 2e5+;
int n;
struct Point{
int x, y;
}a[N], midp[N];
double dis(Point a, Point b){
return sqrt(.*(a.x - b.x)*(a.x - b.x) + .*(a.y - b.y)*(a.y - b.y));
}
bool cmp1(Point a, Point b){
return a.x < b.x;
}
bool cmp2(Point a, Point b){
return a.y < b.y;
}
double solve(int l, int r){
if(l == r ||l + == r) return inf;
if(l + == r) return dis(a[l],a[l+]) + dis(a[l+],a[r]) + dis(a[l],a[r]); int m = l + (r-l)/;
double d1 = solve(l, m);
double d2 = solve(m+, r);
double d = min(d1, d2);
double dd = d/2.0;
double ans = d; int cnt = , i, j, k;
for(i = l; i <= r; ++i)
if(fabs(a[m].x - a[i].x) <= dd)
midp[++cnt] = a[i];
sort(midp+, midp++cnt, cmp2); for(i = ; i < cnt-; ++i){
for(j = i+; j < cnt; ++j){
if(midp[j].y - midp[i].y > dd)
break;
for(k = j+; k <= cnt; ++k){
if(midp[k].y - midp[i].y > dd)
break;
double c = dis(midp[i],midp[j])+dis(midp[j],midp[k])+dis(midp[i],midp[k]);
ans = min(ans, c);
}
}
}
return ans;
}
int main(){
scanf("%d", &n);
for(int i = ; i <= n; ++i)
scanf("%d%d", &a[i].x, &a[i].y);
sort(a+, a++n, cmp1);
printf("%.6lf\n", solve(,n));
return ;
}