M_sea

洛谷4423 [BJWC2011]最小三角形
LuoguBZOJ文化课选手M_sea更博了!分析分治。按照“平面最近点对”那一套理论,选取一条中心线划成两半,这...
扫描右侧二维码阅读全文
12
2019/04

洛谷4423 [BJWC2011]最小三角形

Luogu

BZOJ

文化课选手M_sea更博了!

分析

分治。

按照“平面最近点对”那一套理论,选取一条中心线划成两半,这样子最小三角形会有三种情况:

  • 全部在中心线左边。
  • 全部在中心线右边。
  • 一部分在左边,一部分在右边。

显然第一种和第二种递归下去即可,主要考虑第三种怎么处理。

设当前的最小周长为 $ans$ ,那么先把所有离中心线的 $x$ 的差不超过 $ans$ 的点拿出来按 $y$ 排个序。

枚举一个点 $i$ ,选出所有在它下方的 $y$ 的差不超过 $ans$ 的点,然后在这些点中枚举另外两个顶点。

然后就做完了。具体实现和细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <bitset>
#include <cmath>
#define re register
using namespace std;

template<typename T>
inline T sqr(const T& x) { return x*x; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n;
double ans=2e18;
struct Point { double x,y; } p[N],q[N];

inline int cmpx(Point a,Point b) { return a.x<b.x; }
inline int cmpy(Point a,Point b) { return a.y<b.y; }

inline double dis(Point a,Point b) {
    return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}

inline double calc(Point a,Point b,Point c) {
    return dis(a,b)+dis(b,c)+dis(c,a);
}

inline void solve(int l,int r) {
    if (r-l+1<3) return;
    if (r-l+1==3) {
        ans=min(ans,calc(p[l],p[l+1],p[l+2]));
        return;
    }
    int mid=(l+r)>>1;
    solve(l,mid),solve(mid+1,r);
    double lim=ans/2; int top=0;
    for (re int i=l;i<=r;++i)
        if (fabs(p[i].x-p[mid].x)<=lim) q[++top]=p[i];
    sort(q+1,q+top+1,cmpy);
    for (re int i=1,j=1;i<=top;++i) {
        while (j<=top&&fabs(q[j].y-q[i].y)<=lim) ++j;
        for (re int k=i+1;k<j;++k)
            for (re int l=i+1;l<k;++l)
                ans=min(ans,calc(q[i],q[k],q[l]));
    }
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) p[i].x=read(),p[i].y=read();
    sort(p+1,p+n+1,cmpx); solve(1,n);
    printf("%.6lf\n",ans);
    return 0;
}
最后修改:2019 年 04 月 12 日 08 : 15 PM

发表评论