首页 > 其他分享 >UVA - 10245 The Closest Pair Problem 分治法

UVA - 10245 The Closest Pair Problem 分治法

时间:2023-04-07 11:05:34浏览次数:40  
标签:return Closest min int double mid Pair UVA include


题目大意:给出一系列的点,求出距离最近的两点的距离的大小,如果该距离大于10000,则输出INFINITY,如果不是的话,输出保留四个小数点的距离

解题思路:如果裸的枚举的话,无疑是TLE,O(n^2)的算法既然不行的话,就换分治法试试,将其按X轴坐标的大小排序,由小到大,分别求出每部分的大小,然后进行比较,比较难的合并的过程,会不会存在最短距离的点分别在两个区间之内呢,这是有可能的,所以也要去求,其中的一个剪枝就是,如果左边区间点和中间点的两点的横坐标的差的绝对值小于最短距离的话,或者右边区间的点和中间点亮点的横坐标差小于最短距离的话,那就可以跳过该点了,因为由直角三角形的性质得,斜边永远大于直角边的,斜边就是最短距离,直角边是两个横坐标的差的绝对值

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
const int maxn = 10000 + 5;
double x[maxn],y[maxn];
int r[maxn];
int cmp(const void *p1,const void *p2) {
	int *p = (int *)p1;
	int *q = (int *)p2;
	return x[*p] > x[*q] ? 1:-1;
}

double qrt(int L,int R) {

	return sqrt((x[L] - x[R]) * (x[L] - x[R]) + (y[L] - y[R])*(y[L] - y[R]));
}

double get_min(double a,double b) {
	return a > b ? b:a;	
}

double judge(int L,int R) {
	if(L == R)
		return 100000.0;
	if(L == R-1)
		return qrt(r[L],r[R]);
	double min_ = 100000.0;
	int mid =  (L + R) / 2;
	min_ = get_min(judge(L,mid),judge(mid,R)); 
	double temp;	
	for(int i = mid - 1; i >= L && x[r[mid]] - x[r[L]] < min_; i-- )
		for(int j = mid + 1; j <= R && x[r[R]] - x[r[j]] < min_; j++) {
			temp = qrt(r[i],r[j]);	
			if(temp < min_)
				min_ = temp;	
		}
	return min_;			
}
int main() {
	int num;
	double ans;
	while(scanf("%d", &num) && num) {	
		for(int i = 0; i < num; i++){
			scanf("%lf%lf",&x[i],&y[i]);
			r[i] = i;	
		}

		qsort(r,num,sizeof(r[0]),cmp);	

		ans = judge(0,num-1);	

		if(ans >= 10000.0)
			printf("INFINITY\n");
		else
			printf("%.4lf\n",ans);
	}
	return 0;
}



标签:return,Closest,min,int,double,mid,Pair,UVA,include
From: https://blog.51cto.com/u_10970600/6175572

相关文章

  • UVA - 10905 Children's Game 字符串的排序
    题目大意:给出N个数字串,要求拼出有数字最大的串解题思路:用string就很好解决#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>usingnamespacestd;constintmaxn=60;stringstr[maxn];intcmp(stringa,stringb){ returna+b>b+a;}......
  • UVA - 10706 Number Sequence 子序列
    #include<cstdio>#include<cmath>#include<algorithm>usingnamespacestd;constintmaxn=32761;longlongS[maxn];//存放的是S1,S2,到SK的和,S[5]表示了S1到S4的和,当数字变化到K的时候,一共有多少个字数了intborder[9]={0,1,10,100,1000,10000,100000,1000000,10000000......
  • UVA - 129 Krypton Factor 回溯+剪枝
    题目大意:给出N种字母,要求用这N种字母组成一个困难的串,困难的串指在串中没有相连的两个子串相同,要求输出第M个困难的串解题思路:像八皇后一样,前面判断的就不需要再去判断了,直接往后判断即可#include<cstdio>#include<cstring>intn,L;intans[100];boolflag;intcnt;boolju......
  • Hi-C pairs 文件格式
    Hi-Cpairs文件格式##pairsformatv1.0#sorted:chr1-chr2-pos1-pos2#shape:uppertriangle#chromsize:chr1248956422#chromsize:chr2242193529#chromsize:chr3198295559#chromsize:chr4190214555#chromsize:chr5181538259#chromsize:chr6170805979#ch......
  • Cyborg Genes UVA - 10723
    求一个最短序列,使得输入的两个串的均为他的子序列,同时输出方案数。  n+m-LCS方案数转移时求#include<iostream>#include<cstring>usingnamespacestd;#defineintlonglongintn,m;chara[102],b[102];intf[102][102],cnt[102][102];signedma......
  • 旅行 Tour uva1347
    直角坐标系中,有nn个点。要求先从左往右走,再从右往左走,不重复的经过每一个点。求出最短路径(距离为两点间直线距离)。 f[i][j]表示点1~max(i,j)已走过,的路径长度 #include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<iomanip>......
  • 例题3-2 WERTYU(WERTYU, UVa10082)
    题目把手放在键盘上时,稍不注意就会往右错一位。这样,输入Q会变成输入W,输入J会变成输入K等。键盘如图3-2所示。输入一个错位后敲出的字符串(所有字母均大写),输出打字员本来想打出的句子。输入保证合法,即一定是错位之后的字符串。例如输入中不会出现大写字母A。样例输入OS,GO......
  • 例题3-1 TeX中的引号(Tex Quotes, UVa 272)
    题目在TeX中,左双引号是“``”,右双引号是“''”。输入一篇包含双引号的文章,你的任务是把它转换成TeX的格式。样例输入"Tobeornottobe,"quoththeBard,"thatisthequestion".样例输出``Tobeornottobe,''quoththeBard,``thatisthequestion''.思路依......
  • js中closest()的用法
    JavaScript中的closest()方法用于检索最接近的祖先,或者元素的父项与选择器匹配。如果没有找到祖先,则该方法返回 null 。此方法遍历文档树中的元素及其父元素,并继续遍历......
  • 配置docker容器veth-pair---实现桥接模式
    前言:已知docker网络三种基础模式bridge、host、none,·bridge:桥接模式,创建容器时默认的网络模式;docker安装时,在宿主机内创建一个虚拟网桥docker0,并自动给docker......