首页 > 代码库 > BZOJ2458 [BeiJing2011]最小三角形
BZOJ2458 [BeiJing2011]最小三角形
Description
Xaviera现在遇到了一个有趣的问题。
平面上有N个点，Xaviera想找出周长最小的三角形。
由于点非常多，分布也非常乱，所以Xaviera想请你来解决这个问题。
为了减小问题的难度，这里的三角形也包括共线的三点。
Input
第一行包含一个整数N表示点的个数。
接下来N行每行有两个整数，表示这个点的坐标。
Output
输出只有一行，包含一个6位小数，为周长最短的三角形的周长（四舍五入）。
Sample Input
4
1 1
2 3
3 3
3 4
1 1
2 3
3 3
3 4
Sample Output
3.414214
HINT
100%的数据中N≤200000。
Source
Day1
正解：分治
解题报告：
跟平面最近点对的做法是一样的，只不过在找的时候多一层for就可以了。
不赘述了，代码如下：
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector>10 #include <queue>11 #include <map>12 #include <set>13 using namespace std;14 typedef long long LL;15 const int MAXN = 200011;16 #define RG register17 const double inf = 1e20;18 int n;19 double ans;20 struct node{21 double x,y;22 }a[MAXN],b[MAXN];23 24 inline int getint()25 {26 RG int w=0,q=0; char c=getchar();27 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 28 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w;29 }30 inline bool cmp(node q,node qq){return q.x<qq.x;}31 inline bool cmpy(node q,node qq){return q.y<qq.y;}32 inline double get(RG int i,RG int j){return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));}33 inline double getb(RG int i,RG int j){return sqrt((b[i].x-b[j].x)*(b[i].x-b[j].x)+(b[i].y-b[j].y)*(b[i].y-b[j].y));}34 inline void div_solve(int l,int r){35 if(l==r) return ; if(l+1==r) return ;36 RG int mid=(l+r)/2; div_solve(l,mid); div_solve(mid+1,r); long double dis1,dis2,dis3;37 RG int cnt=0; b[++cnt]=a[mid];38 for(RG int i=mid-1;i>=l;i--) if(a[mid].x-a[i].x<=ans) b[++cnt]=a[i]; else break;39 for(RG int i=mid+1;i<=r;i++) if(a[i].x-a[mid].x<=ans) b[++cnt]=a[i]; else break;40 sort(b+1,b+cnt+1,cmpy);41 for(RG int i=1;i<cnt;i++)42 for(RG int j=i+1;j<cnt;j++) {43 if(fabs(b[i].y-b[j].y)>ans) break; 44 dis1=getb(i,j);45 for(RG int k=j+1;k<=cnt;k++) {46 if(fabs(b[i].y-b[k].y)>ans) break;47 dis2=getb(j,k); dis3=getb(i,k);48 if(dis1+dis2+dis3<ans) ans=dis1+dis2+dis3;49 }50 }51 }52 53 inline void work(){54 n=getint(); for(RG int i=1;i<=n;i++) a[i].x=getint(),a[i].y=getint();55 sort(a+1,a+n+1,cmp); ans=get(n-2,n-1)+get(n-2,n)+get(n-1,n);56 div_solve(1,n);57 printf("%.6lf",ans);58 }59 60 int main()61 {62 work();63 return 0;64 }
BZOJ2458 [BeiJing2011]最小三角形
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。