{"id":354,"date":"2012-05-17T14:46:23","date_gmt":"2012-05-17T06:46:23","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=354"},"modified":"2020-06-06T14:47:04","modified_gmt":"2020-06-06T06:47:04","slug":"%e6%9c%80%e6%8e%a5%e8%bf%91%e7%82%b9%e5%af%b9%ef%bc%8c%e4%b8%80%e7%bb%b4%e5%92%8c%e4%ba%8c%e7%bb%b4%e6%83%85%e5%86%b5","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=354","title":{"rendered":"\u6700\u63a5\u8fd1\u70b9\u5bf9\uff0c\u4e00\u7ef4\u548c\u4e8c\u7ef4\u60c5\u51b5"},"content":{"rendered":"\n
\/\/\u6700\u63a5\u8fd1\u70b9\u5bf9  \u4e00\u7ef4\u60c5\u51b5\npackage wkx;\n \nimport java.io.IOException;\nimport java.util.ArrayList;\nimport java.util.Collections;\nimport java.util.Iterator;\nimport java.util.List;\nimport java.util.Scanner;\n \npublic class Test {\n \n\tprivate static int randomPartition(int[] data, int beg, int end) {\n\t\tint key = data[beg];\n\t\twhile (beg < end) {\n\t\t\twhile (beg < end && data[end] >= key)\n\t\t\t\tend--;\n\t\t\tdata[beg] = data[end];\n\t\t\twhile (beg < end && data[beg] <= key)\n\t\t\t\tbeg++;\n\t\t\tdata[end] = data[beg];\n\t\t}\n\t\tdata[beg] = key;\n\t\treturn beg;\n\t}\n \n\tprivate static int select(int[] data, int beg, int end, int k) {\n\t\tif (beg == end)\n\t\t\t\/\/ return data[beg];\n\t\t\treturn beg;\n\t\tint mid = randomPartition(data, beg, end);\n\t\tint size = mid - beg + 1;\n\t\tif (k <= size)\n\t\t\treturn select(data, beg, mid, k);\n\t\telse\n\t\t\treturn select(data, mid + 1, end, k - size);\n\t}\n \n\tprivate static int min(int a, int b) {\n\t\tif (a > b)\n\t\t\treturn b;\n\t\telse\n\t\t\treturn a;\n\t}\n \n\tprivate static int min(int[] data, int beg, int end) {\n\t\tint min = Integer.MAX_VALUE;\n\t\tfor (int i = beg; i <= end; i++) {\n\t\t\tif (data[i] < min)\n\t\t\t\tmin = data[i];\n\t\t}\n\t\treturn min;\n\t}\n \n\tprivate static int max(int[] data, int beg, int end) {\n\t\tint max = Integer.MIN_VALUE;\n\t\tfor (int i = beg; i <= end; i++) {\n\t\t\tif (data[i] > max)\n\t\t\t\tmax = data[i];\n\t\t}\n\t\treturn max;\n\t}\n \n\tprivate static int CPair(int[] data, int beg, int end) {\n\t\tint len = end - beg + 1;\n\t\tif (len < 2)\n\t\t\treturn Integer.MAX_VALUE;\n\t\tint mid = select(data, beg, end, len \/ 2);\n\t\tint dl = CPair(data, beg, mid);\n\t\tint dr = CPair(data, mid + 1, end);\n\t\tint p = min(data, mid + 1, end) - max(data, beg, mid);\n\t\treturn min(min(dl, dr), p);\n\t}\n \n\tprivate static void print(List<Integer> l) {\n\t\tfor (Iterator<Integer> it = l.iterator(); it.hasNext();)\n\t\t\tSystem.out.println(it.next());\n\t\tSystem.out.println();\n\t}\n \n\tpublic static void main(String[] args) throws IOException {\n\t\tScanner in = new Scanner(System.in);\n\t\tList<Integer> l = new ArrayList<Integer>();\n\t\tint len = 0;\n\t\twhile (in.hasNextInt()) {\n\t\t\tl.add(in.nextInt());\n\t\t\tlen++;\n\t\t}\n\t\tCollections.sort(l);\n\t\tint[] data = new int[len];\n\t\tint t = 0;\n\t\tfor (Iterator<Integer> it = l.iterator(); it.hasNext();)\n\t\t\tdata[t++] = it.next().intValue();\n\t\tSystem.out.println(CPair(data, 0, len - 1));\n\t}\n \n}\n \n\/\/\u6700\u63a5\u8fd1\u70b9\u5bf9 \u4e8c\u7ef4\n \npackage wkx;\n \nimport java.io.IOException;\nimport java.util.ArrayList;\nimport java.util.Collections;\nimport java.util.Iterator;\nimport java.util.List;\nimport java.util.Scanner;\n \npublic class Test {\n\t\/\/ merge\n\tprivate static void Merge(PointY[] Z, PointY[] Y, int beg, int mid, int end) {\n\t\tint l = beg;\n\t\tint r = mid + 1;\n\t\tint k = beg;\n\t\twhile (l <= mid && r <= end) {\n\t\t\tif (Z[l].compareTo(Z[r]) == -1)\n\t\t\t\tY[k++] = Z[l++];\n\t\t\telse\n\t\t\t\tY[k++] = Z[r++];\n\t\t}\n\t\twhile (l <= mid)\n\t\t\tY[k++] = Z[l++];\n\t\twhile (r <= end)\n\t\t\tY[k++] = Z[r++];\n\t}\n \n\t\/\/ distance\n\tprivate static double getDistance(Point a, Point b) {\n\t\tdouble dx = b.x - a.x;\n\t\tdouble dy = b.y - a.y;\n\t\treturn Math.sqrt(Math.abs(dx * dx + dy * dy));\n\t}\n \n\t\/\/ print\n\tprivate static void printX(List<PointX> l) {\n\t\tfor (Iterator<PointX> it = l.iterator(); it.hasNext();)\n\t\t\tSystem.out.println(it.next());\n\t\tSystem.out.println();\n\t}\n\tprivate static void printY(List<PointY> l) {\n\t\tfor (Iterator<PointY> it = l.iterator(); it.hasNext();)\n\t\t\tSystem.out.println(it.next());\n\t\tSystem.out.println();\n\t}\n \n\t\/\/ point\n\tprivate static class Point implements Cloneable{\n\t\tint x;\n\t\tint y;\n \n\t\tpublic String toString() {\n\t\t\treturn \"Point:x=\" + this.x + \" y=\" + this.y;\n\t\t}\n\t}\n \n\t\/\/ pointX\n\tprivate static class PointX extends Point implements Comparable {\n\t\tpublic int compareTo(Object o) {\n\t\t\tPointX p = (PointX) o;\n\t\t\tif (p.x < this.x)\n\t\t\t\treturn 1;\n\t\t\telse if (p.x == this.x)\n\t\t\t\treturn 0;\n\t\t\telse\n\t\t\t\treturn -1;\n\t\t}\n\t}\n \n\t\/\/ PointY\n\tprivate static class PointY extends Point implements Comparable {\n\t\tint pos;\n \n\t\tpublic int compareTo(Object o) {\n\t\t\tPointY p = (PointY) o;\n\t\t\tif (p.y < this.y)\n\t\t\t\treturn 1;\n\t\t\telse if (p.y == this.y)\n\t\t\t\treturn 0;\n\t\t\telse\n\t\t\t\treturn -1;\n\t\t}\n\t}\n\t\/\/min \n\tprivate static double min(double a, double b) {\n\t\tif (a > b)\n\t\t\treturn b;\n\t\telse\n\t\t\treturn a;\n\t}\n\t\/\/closest\n\tprivate static double closest(PointX[] X, PointY[] Y, PointY[] Z, int beg,\n\t\t\tint end, Point a, Point b) {\n\t\t\/\/ only two points\n\t\tif (end - beg == 1) {\n\t\t\ta.x = X[beg].x;\n\t\t\ta.y = X[beg].y;\n\t\t\tb.x = X[end].x;\n\t\t\tb.y = X[end].y;\n\t\t\treturn getDistance(a, b);\n\t\t}\n\t\t\/\/ three Points\n\t\tif (end - beg == 2) {\n\t\t\tdouble d1 = getDistance(X[beg], X[beg + 1]);\n\t\t\tdouble d2 = getDistance(X[beg + 1], X[end]);\n\t\t\tdouble d3 = getDistance(X[beg], X[end]);\n\t\t\tif (d1 <= d2 && d1 <= d3) {\n\t\t\t\ta.x = X[beg].x;\n\t\t\t\ta.y = X[beg].y;\n\t\t\t\tb.x = X[beg + 1].x;\n\t\t\t\tb.y = X[beg + 1].y;\n\t\t\t\treturn d1;\n\t\t\t} else if (d2 <= d1 && d2 <= d3) {\n\t\t\t\ta.x = X[beg + 1].x;\n\t\t\t\ta.y = X[beg + 1].y;\n\t\t\t\tb.x = X[end].x;\n\t\t\t\tb.y = X[end].y;\n\t\t\t\treturn d2;\n\t\t\t} else {\n\t\t\t\ta.x = X[beg].x;\n\t\t\t\ta.y = X[beg].y;\n\t\t\t\tb.x = X[end].x;\n\t\t\t\tb.y = X[end].y;\n\t\t\t\treturn d3;\n\t\t\t}\n\t\t}\n\t\t\/\/ more than three\n\t\tint mid = (beg + end) \/ 2;\n\t\tint l = beg;\n\t\tint r = mid + 1;\n\t\tfor (int i = beg; i <= end; i++) {\n\t\t\tif (Y[i].pos > mid)\n\t\t\t\tZ[r++] = Y[i];\n\t\t\telse\n\t\t\t\tZ[l++] = Y[i];\n\t\t}\n\t\tdouble dl = closest(X, Z, Y, beg, mid, a, b);\n\t\tPoint ar = new Point();\n\t\tPoint br = new Point();\n\t\tdouble dr = closest(X, Z, Y, mid + 1, end, ar, br);\n\t\tif (dl > dr) {\n\t\t\ta.x = ar.x;\n\t\t\tb.x = br.x;\n\t\t\ta.y = ar.y;\n\t\t\tb.y = br.y;\n\t\t}\n\t\tdouble d = min(dl, dr);\n\t\t\/\/ rebuild Y\n\t\tMerge(Z, Y, beg, mid, end);\n \n\t\tint k = beg;\n\t\tfor (int i = beg; i <= end; i++) {\n\t\t\tif (Math.abs(Y[mid].x - Y[i].x) < d) {\n\t\t\t\tZ[k++]=Y[i];\n\t\t\t}\n\t\t}\n\t\t\n\t\tfor(int i=beg;i<=end;i++){\n\t\t\tfor(int j=i+1;j<k&&(Z[j].y-Z[i].y<d);j++){\n\t\t\t\tdouble dp=getDistance(Z[i],Z[j]);\n\t\t\t\tif(dp<d){\n\t\t\t\t\td=dp;\n\t\t\t\t\ta.x=Z[i].x;\n\t\t\t\t\tb.x=Z[j].x;\n\t\t\t\t\ta.y=Z[i].y;\n\t\t\t\t\tb.y=Z[j].y;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\t\/\/ return\n\t\treturn d;\n\t}\n\t\/\/main\n\tpublic static void main(String[] args) throws IOException {\n\t\t\/\/ read Array\n\t\tScanner in = new Scanner(System.in);\n\t\tList<PointX> X = new ArrayList<PointX>();\n\t\tList<PointY> Y = new ArrayList<PointY>();\n\t\tint num = 0;\n\t\twhile (in.hasNextInt()) {\n\t\t\tPointX pX = new PointX();\n\t\t\tPointY pY = new PointY();\n\t\t\tpX.x = pY.x = in.nextInt();\n\t\t\tpX.y = pY.y = in.nextInt();\n\t\t\tpY.pos = num++;\n\t\t\tX.add(pX);\n\t\t\tY.add(pY);\n\t\t}\n\t\t\/\/sort\n\t\tCollections.sort(X);\n\t\tCollections.sort(Y);\n\t\tprintX(X);\n\t\tprintY(Y);\n\t\t\/\/ copy to array\n\t\tPointX[] Xs = new PointX[num];\n\t\tPointY[] Ys = new PointY[num];\n\t\tIterator<PointX> itX = X.iterator();\n\t\tIterator<PointY> itY = Y.iterator();\n\t\tfor (int i = 0; i < num; i++) {\n\t\t\tXs[i] = itX.next();\n\t\t\tYs[i] = itY.next();\n\t\t}\n \n\t\tPointY[] Zs = new PointY[num];\n\t\tPoint a = new Point();\n\t\tPoint b = new Point();\n\t\tdouble dis = closest(Xs, Ys, Zs, 0, num - 1, a, b);\n\t\tSystem.out.println(a);\n\t\tSystem.out.println(b);\n\t\t\n\t\tSystem.out.println(\"Point A:[\" + a.x + \",\" + a.y + \"]\" + \" Point B:[\"\n\t\t\t\t+ b.x + \",\" + b.y + \"]\" + \" Distance:\" + dis);\n\t\n\t\t\/*Random rand=new Random(new Date().getTime());\n\t\tfor(int i=1;i<=100;i++){\n\t\t\tSystem.out.println(rand.nextInt()+\" \"+rand.nextInt());\n\t\t}*\/\n\t}\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-354","post","type-post","status-publish","format-standard","hentry","category-06-03-play-ground"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/354","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=354"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/354\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=354"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=354"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=354"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}