http://www.lydsy.com/JudgeOnline/problem.php?id=2458

[BeiJing2011]最小三角形

描述

Frisk现在遇到了一个有趣的问题。

平面上有N个点，Frisk想找出周长最小的三角形。

由于点非常多，分布也非常乱，所以Frisk想请你来解决这个问题。

为了减小问题的难度，这里的三角形也包括共线的三点。

输入

第一行包含一个整数N表示点的个数。

接下来N行每行有两个整数，表示这个点的坐标。

输出

输出只有一行，包含一个6位小数，为周长最短的三角形的周长（四舍五入）。

样例

提示

100%的数据中N≤200000。

考试时失了智，只拿了半个暴力分

其实这和平面最近点对方法一毛一样

除了多了一层循环

代码蒯上

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

inline int gotcha()

{

	register int a=0;bool b=1;register char c=getchar();

	while(c>'9' || c<'0'){if(c=='-')b=0;c=getchar();}

	while(c>='0' && c<='9')a=a*10+c-48,c=getchar();

	return b?a:-a;

}

const double EPS = 1e-9;

const int _ = 200002;

using namespace std;

struct point{double x,y;}p[_];

inline bool init_cmp(const point &a,const point &b){return a.x<b.x;}

inline bool cmp(const int &a,const int &b){return p[a].y<p[b].y;}

inline double xdis(const int &a,const int &b){return fabs(p[a].x-p[b].x);}

inline double ydis(const int &a,const int &b){return fabs(p[a].y-p[b].y);}

double dist(int a,int b){return sqrt(xdis(a,b)*xdis(a,b)+ydis(a,b)*ydis(a,b));}

int n,q[_],lq;

double finder(int l,int r)

{

	if(r<l+2)return 1e33;

	int i,j,k,mid=(l+r)>>1;

	double dis=min(finder(l,mid),finder(mid+1,r));

	lq=0;

	for(i=l;i<=r;i++)if(xdis(i,mid)<=dis/2)q[++lq]=i;

	sort(q+1,q+lq+1,cmp);

	for(i=1;i<=lq-2;i++)

		for(j=i+1;j<=lq-1 && ydis(q[i],q[j])<=dis/2;j++)

			for(k=j+1;k<=lq && ydis(q[i],q[k])<=dis/2;k++)

				dis=min(dis,dist(q[i],q[j])+dist(q[j],q[k])+dist(q[i],q[k]));

	return dis;

}

int main()

{

	register int i;

	n=gotcha();

	for(i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);

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

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

	return 0;

}

巴特西

分治 - 计算几何 - BZOJ2458,[BeiJing2011]最小三角形

[BeiJing2011]最小三角形

描述

输入

输出

样例

提示

最新文章

热门文章