zancun

#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
int n,m,i,j,ans;
double x,y;
vector<pair<double,double>/**/> po;
bool cmp(int x,int y)
{
    if (po[x].second==po[y].second)
        return po[x].first<po[y].first;
    return po[x].second<po[y].second;
}
double dfs(int l,int r)
{
    int i,j;
    if (l+1==r)
    {
        return sqrt(sqr(po[l].first-po[r].first)+sqr(po[l].second-po[r].second));
    }
    if (l==r)
    {
        return 1e10;
    }
    double res=min(dfs(l,(l+r)/2),dfs((l+r)/2+1,r));
    vector<int> pos;
    for (i=l;i<=r;i++)
    {
        if (abs(po[i].second-po[(l+r)/2].second)<res)
        {
            pos.push_back(i);
        }
    }
    sort(pos.begin(),pos.end(),cmp);
    for (i=0;i<pos.size();i++)
    {
         for (j=i+1;j<=i+6&&j<pos.size();j++)
         {
            res=min(res,sqrt(sqr(po[pos[i]].first-po[pos[j]].first)+sqr(po[pos[i]].second-po[pos[j]].second)));
         }
    }
    return ans;
}
int main()
{
    cin>>n;
    for (i=1;i<=n;i++)
    {
        cin>>x>>y;
        po.push_back(make_pair(x,y));
    }
    sort(po.begin(),po.end());
    printf("%.3f\n",dfs(0,n-1));
    return 0;
}

0 条评论

目前还没有评论...

信息

ID
1000
难度
9
分类
(无)
标签
(无)
递交数
57540
已通过
23239
通过率
40%