题解：P4423 [BJWC2011] 最小三角形

DarkClever · 2024-11-11 16:01:55 · 题解

我们充分发扬人类智慧。

考虑给所有点加上一个玄学常数后按 x\times y 排序。

根据数学直觉，能构成最小三角形的点一定在数组中相邻，所以我们只取前 20 个点统计答案。

考虑到出题人是懒惰的，只会出小数据来卡我们，不会出大数据来卡我们，于是就在 n\leq 700 时使用暴力，这样程序跑的飞起，n\leq 2\times 10^5 的时候也可以在 323ms 内通过。

#include<bits/stdc++.h>
using namespace std;
struct node{
    long long x,y;
}a[210000];
bool cmp(node x,node y){
    return (x.x+114514)*(x.y+114514) < (y.x+114514)*(y.y+114514);
}
double dis(node x,node y){
    return sqrt((x.x - y.x)*(x.x - y.x) + (x.y - y.y)*(x.y - y.y));
}
double getans(node x,node y,node z){
    // cout<<dis(x,y)+dis(x,z)+dis(y,z)<<endl;
    double ans = dis(x,y)+dis(x,z)+dis(y,z);
    return fabs(ans);
}
int xx = 0;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    double minn = 1000000000;
    for(int i=1;i<=n;i++){
        long long x,y;
        cin>>x>>y;
        a[i].x = x,a[i].y = y;
    }
    if(n<=700){
        for(int i=1;i<=n;i++){
            for(int j=1;j<i;j++){
                for(int k=1;k<j;k++){
                    minn = min(minn,getans(a[i],a[j],a[k]));

                }
            }
        }
        cout<<fixed<<setprecision(6)<<minn<<endl;
        return 0;
    }

    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        // cout<<i<<endl;
        for(int j=max(i-19,1);j<i;j++){
            // cout<<j<<endl;
            for(int k=max(j-19,1);k<j;k++){
                // cout<<k<<endl;
                minn = min(getans(a[i],a[j],a[k]),minn);
            }
        }
    }
    cout<<fixed<<setprecision(6)<<minn<<endl;
    return 0;
}