- A+B Problem
- 2017-12-22 17:46:56 @
#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
- 分类
- (无)
- 标签
- (无)
- 递交数
- 74382
- 已通过
- 28459
- 通过率
- 38%
- 被复制
- 220