题目链接:

  https://vijos.org/p/1012

题目大意

  给n个坐标(n<=100 000),求直线距离最短是多少。数据较大用long long 或 double

题目思路:

  【枚举】

  正解貌似是分治,不过我一看就暴力枚举+剪枝了。

  先按x y为第一、第二关键字排序。

  设当前最优解为c,如果当前的点对x坐标差的平方比最优解大就可以break了。

   

  

 //
//by coolxxx
//
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define eps 1e-8
#define J 10000
#define MAX 0x7f7f7f7f
#define PI 3.1415926535897
#define N 100004
using namespace std;
int n,m,lll,ans,cas;
double b,c;
struct xxx
{
double x,y;
}a[N];
bool cmp(xxx aa,xxx bb)
{
if(aa.x!=bb.x)return aa.x<bb.x;
return aa.y<bb.y;
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
// while(~scanf("%s%d",s,&n))
while(~scanf("%d",&n) && n)
{
c=;
for(i=;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+,a++n,cmp);
for(i=;i<=n;i++)
{
for(j=i+;j<=n;j++)
{
if(sqr(a[i].x-a[j].x)>c)break;
b=sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y);
c=min(c,b);
}
}
c=sqrt(c);
printf("%.3lf\n",c);
}
return ;
} /*
// //
*/

最新文章

  1. ASP.net页面代码执行顺序
  2. VS中两个常用辅助工具
  3. K2 BPM医疗行业EMS解决方案
  4. 通过AssetsLibrary框架访问所有相片
  5. 使用spring+hibernate+atomikos+tomcat构建分布式事务
  6. node.js常用的几个模块总结
  7. Swift3.0服务端开发(二) 静态文件添加、路由配置以及表单提交
  8. UI培训怎么学才高效
  9. 测评:华为最新移动应用/APP测试工具MobileTest
  10. application-config.xml和mvc-config.xml的区别
  11. C博客作业01--分支、顺序结构
  12. time、datetime、calendar
  13. 使用window.performance分析web前端性能
  14. python变量存储
  15. 20165214 2018-2019-2 《网络对抗技术》Exp1 PC平台逆向破解 Week3
  16. python-----编写接口,使用postman与soapiu与jemeter访问调用
  17. DOM获取元素的方法
  18. JavaWeb学习 (二十八)————文件上传和下载
  19. JMX堆栈分析
  20. Matplotlib 知识点整理

热门文章

  1. python爬虫scrapy的Selectors参考文档
  2. bootstrap 下的 validation插件
  3. 如何设置MySQL Workbench EER Diagram 尺寸?
  4. ORACLE 中ROWNUM用法总结!(转)
  5. ResultSetMetaData rsmd = rs.getMetaData()是什么意思?
  6. iOS socket编程
  7. VisualStudio2013内置SQLServer入门
  8. java_设计模式_装饰者模式_Decorator Pattern(2016-07-28)
  9. 【BZOJ3295】【块状链表+树状数组】动态逆序对
  10. Android开发系列----sdk下载 环境准备