【枚举】Vijos P1012 清帝之惑之雍正
2024-10-19 14:35:49
题目链接:
题目大意:
给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 ;
} /*
// //
*/
最新文章
- ASP.net页面代码执行顺序
- VS中两个常用辅助工具
- K2 BPM医疗行业EMS解决方案
- 通过AssetsLibrary框架访问所有相片
- 使用spring+hibernate+atomikos+tomcat构建分布式事务
- node.js常用的几个模块总结
- Swift3.0服务端开发(二) 静态文件添加、路由配置以及表单提交
- UI培训怎么学才高效
- 测评:华为最新移动应用/APP测试工具MobileTest
- application-config.xml和mvc-config.xml的区别
- C博客作业01--分支、顺序结构
- time、datetime、calendar
- 使用window.performance分析web前端性能
- python变量存储
- 20165214 2018-2019-2 《网络对抗技术》Exp1 PC平台逆向破解 Week3
- python-----编写接口,使用postman与soapiu与jemeter访问调用
- DOM获取元素的方法
- JavaWeb学习 (二十八)————文件上传和下载
- JMX堆栈分析
- Matplotlib 知识点整理
热门文章
- python爬虫scrapy的Selectors参考文档
- bootstrap 下的 validation插件
- 如何设置MySQL Workbench EER Diagram 尺寸?
- ORACLE 中ROWNUM用法总结!(转)
- ResultSetMetaData rsmd = rs.getMetaData()是什么意思?
- iOS socket编程
- VisualStudio2013内置SQLServer入门
- java_设计模式_装饰者模式_Decorator Pattern(2016-07-28)
- 【BZOJ3295】【块状链表+树状数组】动态逆序对
- Android开发系列----sdk下载 环境准备