题意,很简单,给n个点的坐标,求距离最近的一对点之间距离的一半。

第一行是一个数n表示有n个点,接下来n行是n个点的x坐标和y坐标。实数。

这个题目其实就是求最近点对的距离

 

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std; //①按照每个点 x 值由小到大进行排序,若 x 相同,则按照 y 由小到大进行排序,计算相邻两点的最短距离,即为len1。
//②按照每个点 y 值由小到大进行排序,若 y 相同,则按照 x 由小到大进行排序,计算相邻两点的最短距离,即为len2。
//答案即为:min(len1,len2)。 struct Point
{
double x;
double y;
}coor[100001]; bool cmp1(const Point a,const Point b)
{
if(a.x<b.x)
return true;
if(a.x>b.x)
return false;
else
return a.y<b.y;
} bool cmp2(const Point a,const Point b)
{
if(a.y<b.y)
return true;
if(a.y>b.y)
return false;
else
return a.x<b.x;
} double num(int i,int j)
{
return sqrt( pow( (coor[i].x-coor[j].x),2 ) + pow( (coor[i].y-coor[j].y),2 ) ); //计算两点之间的距离
} int main()
{
double radius=0; //定义半径
int i,N;
while(scanf("%d",&N) && N!=0) //N大于2小于100000
{
for(i=1 ; i<=N ; i++)
scanf("%lf %lf",&coor[i].x , &coor[i].y);
sort(coor+1,coor+N+1,cmp1); //先排x轴
radius=num(1,2);
for(i=2;i<N;i++)
{
if( radius>num(i,i+1) )
radius=num(i,i+1);
}
sort(coor+1,coor+N+1,cmp2); //再排y轴
for(i=1;i<N;i++)
{
if( radius>num(i,i+1) )
radius=num(i,i+1);
}
printf("%.2f\n",radius/2);
}
return 0;
} sort函数:

firstlast

分别指向被排序序列中初始及末尾位置的随机访问迭代器(Random-access Iterators)。这个范围即 [first,last) ,包括 first 到 last 间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。

comp

二元谓词(Binary)函数,以两个元素为参数,然后返回一个可转换成 bool 类型的值。

其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

该函数不能修改其参数。

可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

最新文章

  1. clojure 之 hello world
  2. dyld: Library not loaded: /System/Library/Frameworks/UserNotifications.framework/UserNotifications解决办法
  3. Js原生 双向数据绑定
  4. JS逗号运算符的用法详解
  5. 《理解 ES6》阅读整理:块绑定(Block Binding)
  6. smartUpload组件文件上传
  7. alibaba笔试
  8. Docker系列(二)组件介绍
  9. JavaScript之数据类型
  10. PHP数组操作——获取数组最后一个值的方法
  11. 深入理解Java的protected修饰符
  12. 获取多个div,点击第几个,显示第几个
  13. Leetcode - Jump Game Two
  14. 约瑟夫环(java面向对象实现)
  15. IOS开发中如何判断程序第一次启动(根据判断结果决定是否显示新手操作引导)
  16. SQL优化方法:
  17. insert into select的实际用法
  18. django 之 stark组件
  19. python编写文件统计脚本
  20. CSS3:透明度

热门文章

  1. Java - 错误: &amp;quot;java.lang.ArrayIndexOutOfBoundsException: length=1; index=1&amp;quot;
  2. Java-WebSocket
  3. Java反编译器安装及各版本介绍
  4. PHP获取Cookie模拟登录CURL(转)
  5. SecureCRT 中 python 命令行使用退格键(backspace)出现 ^H 解决办法
  6. linux下grep命令笔记
  7. file is missing from source location:c\temp\batang.ttc
  8. JQuery AJAX请求aspx后台方法
  9. bootstrap.css.map这个文件有何用处?该怎能使用它?
  10. FOR XML PATH 转换问题