|
题目大意：给定平面上的一个点集，求这个点集所能组成的周长最小的三角形
与平面最近点对一个道理- - 这个题也是分治做法
做法如下：
1.记录全局答案ans
2.将所有点按照x值排序
3.定义Solve(l,r)为处理[l,r]区间内的最小三角形
4.对于每层Solve(l,r)，将当前区间分成左右两部分，分别递归处理
5.两侧的最小三角形都以处理完毕，现在我们要处理的就是两区间之间的点构成的三角形
6.将本层中与点mid的横坐标之差不超过ans/2的点拎出来，按照纵坐标排序 (其实这步可以直接递归退出时归并排序)
7.维护双指针，保证内部纵坐标之差不超过ans/2，对于每个点在范围内暴力查找最小三角形即可
时间复杂度期望O(nlogn)...吧？
为何随便写了一发就进第一篇了- -
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 200200
#define INF 1e10
#define EPS 1e-7
using namespace std;
struct Point{
int x,y;
Point() {}
Point(int _,int __):
x(_),y(__) {}
friend istream& operator >> (istream &_,Point &p)
{
scanf("%d%d",&p.x,&p.y);
return _;
}
friend double Distance(const Point &p1,const Point &p2)
{
return sqrt( (double)(p1.x-p2.x)*(p1.x-p2.x) + (double)(p1.y-p2.y)*(p1.y-p2.y) );
}
}points[M],_points[M];
bool Compare1(const Point &p1,const Point &p2)
{
return p1.x < p2.x;
}
bool Compare2(const Point &p1,const Point &p2)
{
return p1.y < p2.y;
}
int n;
double ans=INF;
void Solve(int l,int r)
{
if(l==r) return ;
if(l+1==r)
{
if( Compare2(points[r],points[l]) )
swap(points[l],points[r]);
return ;
}
int i,j,k,tail,mid=l+r>>1,temp=points[mid].x;
Solve(l,mid);Solve(mid+1,r);
int l1=l,l2=mid+1;
for(i=l;i<=r;i++)
{
if( l2>r || l1<=mid && Compare2(points[l1],points[l2]) )
_points[i]=points[l1++];
else
_points[i]=points[l2++];
}
memcpy(points+l,_points+l,sizeof(Point)*(r-l+1) );
for(i=l,tail=l;i<=r;i++)
if(abs(points[i].x-temp)<ans/2)
{
for(;points[i].y-points[tail].y>ans/2;tail++);
for(j=tail;j<i-1;j++)
if(abs(points[j].x-temp)<ans/2)
if(points[i].y-points[j].y<ans/2)
for(k=j+1;k<i;k++)
ans=min(ans,Distance(points[i],points[j])+Distance(points[i],points[k])+Distance(points[j],points[k]) );
}
}
int main()
{
//freopen("2458.in","r",stdin);
//freopen("2458.out","w",stdout);
int i;
cin>>n;
for(i=1;i<=n;i++)
cin>>points[i];
sort(points+1,points+n+1,Compare1);
Solve(1,n);
printf("%.6lf\n",ans);
return 0;
}
| 
转播
