【题目链接】

http://acm.hdu.edu.cn/showproblem.php?pid=1007

【算法】

答案为平面最近点对距离除以2

【代码】

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXN 100010
const double INF = 1e10; struct info
{
double x,y;
} a[MAXN]; int n,i; inline bool cmpx(info a,info b)
{
return a.x < b.x;
}
inline bool cmpy(info a,info b)
{
return a.y < b.y;
}
inline double dist(info p,info q)
{
return sqrt(abs(p.x - q.x) * abs(p.x - q.x) + abs(p.y - q.y) * abs(p.y - q.y));
}
inline double Closest_Pair(int l,int r)
{
int i,j,mid,len = ;
static info s[MAXN];
double d;
if (l == r) return INF;
if (l + == r) return dist(a[l],a[r]);
mid = (l + r) >> ;
d = min(Closest_Pair(l,mid),Closest_Pair(mid+,r));
for (i = l; i <= r; i++)
{
if (abs(a[mid].x - a[i].x) <= d) s[++len] = a[i];
}
sort(s+,s+len+,cmpy);
for (i = ; i <= len; i++)
{
for (j = i + ; j <= len && s[j].y - s[i].y <= d; j++)
{
d = min(d,dist(s[i],s[j]));
}
}
return d;
} int main()
{ while (scanf("%d",&n) && n)
{
for (i = ; i <= n; i++) scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+,a+n+,cmpx);
printf("%.2lf\n",Closest_Pair(,n) / 2.0);
} return ; }

最新文章

  1. 自定义view(一)
  2. Python标准模块--import
  3. mysql: symbol lookup error: /usr/local/lib/libreadline.so.6: undefined symbol: UP
  4. IE下angularJS页面跳转的bug
  5. Java语法基础(三)----选择结构的if语句、switch语句
  6. [daily][network] NAT原理(转)
  7. kfed (kernel file editor:内核文件编辑器)
  8. Ubuntu Linux 下文件名乱码(无效的编码)的快速解决办法
  9. css/js online online code editor/formator/debuger
  10. Parallel stepped for loops in .NET C# z
  11. VC CArchive类使用
  12. BFC,IFC,GFC,FFC的定义及功能
  13. virus.win32.parite.H病毒的查杀方法
  14. UVA662- Fast Food
  15. DOM&amp;JavaScript示例&amp;练习
  16. Python XML解析之ElementTree
  17. 如何突破Ue4材质编辑器没有Pass的概念
  18. Comparer Under Centos 7
  19. 多线程Java Socket编程
  20. win10系统安装labelImg

热门文章

  1. Angular ZoneJS 原理
  2. 01Hypertext Preprocessor
  3. Django线上部署教程:腾讯云+Ubuntu+Django+Uwsgi(转载)
  4. Jquery 上一步、下一步及提交
  5. Invalid ON UPDATE clause for &#39;create_date&#39; column
  6. JSP页面中的动作标识
  7. calculate Cp history (from Fluent) using Matlab
  8. Webstorm如何配置自动补全前缀--autoprefixer
  9. Codeforces Round #228 (Div. 2)
  10. 1874 Bellman-ford算法 队列优化过的 用于稀疏图,有负权的图