[ZJU 2107]Quoit Design(平面最近点对)

本文主要是介绍[ZJU 2107]Quoit Design(平面最近点对)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目大意】：

给你N个点，求最近的两个点的距离，然后除以2输出。

【题目分析】：

这个就是经典的平面最近点对问题。求法就是分支策略，不断地二分，然后取最小。然后需要注意的就是越过中线的点对的处理。

其实那个很猥琐，想法就是找出变长为2ans*ans的矩形，然后进行枚举。这里有个很诡异的结论，就是这个矩形当中的点数不会超过8。

大致流程：

1、先按照x和y坐标进行排序
2、调用分治程序
3、分情况讨论
4、若是一个点则返回无穷大
5、若是两个点则返回两点之间的距离
6、若是多个点则分治
7、合并，查看是否最近点对是否跨立于左右区域
8、假设当前最近点对距离为ans，则寻找在2ans*ans的矩形范围内点
9、可以证明，2ans*ans这个矩形的点不超过8个，之后进行枚举
10、得出最近点对

【代码(很丑，大家尽情鄙视~)】：

program ZJU_2107; const inf=10e31; type situ=record x,y:real; end; var tmp,a:array[1..100000] of situ; ans:real; n,i:longint; procedure qsort(s,t:longint); var i,j:longint; key:real; k:situ; begin i:=s; j:=t; key:=a[(s+t) div 2].x; repeat while a[i].x<key do inc(i); while a[j].x>key do dec(j); if i<=j then begin k:=a[i]; a[i]:=a[j]; a[j]:=k; inc(i); dec(j); end; until i>j; if s<j then qsort(s,j); if i<t then qsort(i,t); end; procedure qsorty(s,t:longint); var i,j:longint; key:real; k:situ; begin i:=s; j:=t; key:=tmp[(s+t) div 2].y; repeat while tmp[i].y<key do inc(i); while tmp[j].y>key do dec(j); if i<=j then begin k:=tmp[i]; tmp[i]:=tmp[j]; tmp[j]:=k; inc(i); dec(j); end; until i>j; if s<j then qsort(s,j); if i<t then qsort(i,t); end; procedure find(s,t:longint); var i,j,mid,tot:longint; temp,midl:real; begin if s=t then exit; if s=t+1 then begin temp:=sqrt(sqr(a[s].x-a[t].x)+sqr(a[s].x-a[t].y)); if temp<ans then ans:=temp; exit; end; mid:=(s+t) div 2; midl:=(a[mid].x+a[mid+1].x)/2; find(s,mid); find(mid+1,t); tot:=0; for i:=s to t do if abs(a[i].x-midl)<ans then begin inc(tot); tmp[tot].x:=a[i].x; tmp[tot].y:=a[i].y; end; qsorty(1,tot); for i:=1 to tot-1 do for j:=i+1 to i+8 do begin if j>tot then break; temp:=sqrt(sqr(tmp[i].x-tmp[j].x)+sqr(tmp[i].y-tmp[j].y)); if temp<ans then ans:=temp; end; end; begin assign(input,'a.in'); assign(output,'a.out'); reset(input); rewrite(output); while true do begin readln(n); if n=0 then break; for i:=1 to n do readln(a[i].x,a[i].y); qsort(1,n); ans:=inf; find(1,n); writeln(ans/2:0:2); end; close(input); close(output); end. 

这篇关于[ZJU 2107]Quoit Design(平面最近点对)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---