hdu1007最近点对问题（分冶java）

题目链接
题意就是给若干点，求最近点对问题。

• 首先这题是我很久前看到的，我那时候用了o（n^2）因为数据量太大，计算太多超时。当时看了别人的分析就说分冶当时看代码太长也就没静下心看。前天翻了数据结构看到分冶算法的最近点问题恍然大悟，一下子就懂了。理解了其中的奥秘。
• 对于分冶的问题，就是一个问题可以拆成若干个子问题，若干个子问题之间没有联系，并且这个问题的处理方法同样适用于子问题。
  首先上图
  

如果用最暴力的方法，那么我们就是要将每两个点计算一遍，比较大小。如果有n个点，那么就要计算n^2次。我们下面进行初步优化：

取中间点，先算出所有左侧点的距离最小值，再算出右侧距离最小值，这两个中更小的那个为min。这个距离不一定是最短的那个点，因为有可能最短的那个点再中间跨越两边。

• 我们思考一下，这个中间两点一个在左，一个在右，两个点的横坐标之差一定小于 min不然他的投影都大于最短，所以我只需要处理中间左右区间为min里面的点进行处理，对于这些点，左右距离是小于min的，如果上下距离大于min，就跳过不在考虑。
• 考虑一下计算量，左侧（n^2） /4 右侧 也是，加起来是n*n/2,再加上中间的部分数据。这是一次优化的，另外，对于海量数据，我们分析其左侧，我们也可以把左侧拆成一半，先算左右再算中间，右侧也是如此。并且问题可以一直拆分直到不能在拆为止。这个复杂度的差距就出来了。
• 但是对于这个题，如果取x排序分冶事件耗费也比较大，这个可能就是点都大部分聚集在中间，上下间距较大的缘故，我们采用y排序划分分冶。效率还是很高的。
  附上代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class Main { static int n; public static void main(String[] args) throws IOException { StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); //List<node>list=new ArrayList(); while(in.nextToken()!=StreamTokenizer.TT_EOF) { n=(int)in.nval;if(n==0) {break;} node no[]=new node[n]; for(int i=0;i<n;i++) { in.nextToken();double x=in.nval; in.nextToken();double y=in.nval; // list.add(new node(x,y)); no[i]=new node(x,y); } Arrays.sort(no, com); double min= search(no,0,n-1); out.println(String.format("%.2f", Math.sqrt(min)/2));out.flush(); } } private static double search(node[] no, int left,int right) { int mid=(right+left)/2; double minleng=0; if(left==right) {return Double.MAX_VALUE;} else if(left+1==right) {minleng= (no[left].x-no[right].x)*(no[left].x-no[right].x)+(no[left].y-no[right].y)*(no[left].y-no[right].y);} else minleng= min(search(no,left,mid),search(no,mid,right)); int ll=mid;int rr=mid+1; while(no[mid].y-no[ll].y<=Math.sqrt(minleng)/2&&ll-1>=left) {ll--;} while(no[rr].y-no[mid].y<=Math.sqrt(minleng)/2&&rr+1<=right) {rr++;} for(int i=ll;i<rr;i++) { for(int j=i+1;j<rr+1;j++) { double team=0; if(Math.abs((no[i].x-no[j].x)*(no[i].x-no[j].x))>minleng) {continue;} else { team=(no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y); if(team<minleng)minleng=team; } } } return minleng; } private static double min(double a, double b) { // TODO 自动生成的方法存根 return a<b?a:b; } static Comparator<node>com=new Comparator<node>() { @Override public int compare(node a1, node a2) { // TODO 自动生成的方法存根 return a1.y-a2.y>0?1:-1; }}; static class node { double x; double y; public node(double x,double y) { this.x=x; this.y=y; } }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
 

如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/82829615