<h1 id="heading">题目</h1>
{% fold 点击显/隐题目 %}
<div class="oj"><div class="part" title="Description">
给定平面上n个点，找出其中的一对点的距离，使得这n个点的所有点对中，该距离为所有点对中最小的。
</div><div class="part" title="Input">
第一行：n；2≤n≤60000；
接下来n行：每行两个整数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。
</div><div class="part" title="Output">
仅一行，一个实数，表示最短距离，精确到小数点后面4位。
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
3
1 1
1 2
2 2
</div><div class="output part" title="Sample Output">
1.0000
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
正确思路好像要用主席树,然而不会,只能暴力写一发
首先可以知道如果按照 <code>(x,y)</code> 排序,可以发现离得近的点普遍距离较近 
存在反例,<code>(1,1)</code> <code>(1,100)</code> <code>(2,1)</code> 排序后显然第一个和第三个距离更近
但是在已经范围内我们可以近似认为没影响(比较的时候多比较几组就行了~)
那么我们尝试采用二分进行优化 
用 <code>dfs(l,r)</code> 来表示 <code>[l,r)</code> 的最近的两个点的距离
显然有:
<ol>
<li>最近的两个点可能全部在 <code>mid</code> 左侧的范围里,也即 <code>dfs(l,mid)</code></li>
<li>最近的两个点可能全部在 <code>mid</code> 右侧的范围里,也即 <code>dfs(mid,r)</code></li>
<li>最近的两个点一个在 <code>mid</code> 左侧,一个在 <code>mid</code> 右侧</li>
</ol>
前两种情况都比较容易解决,只需要考虑最后一种情况 
遍历两侧的所有点,计算他们的距离最小值
根据最上面的说明,可以得知横跨 <code>mid</code> 左右的距离最近的点必然距离 <code>mid</code> 距离不远 
可以将 <code>x1-x2</code> 近似看成距离,如果它已经大于之前已经获得最小距离,可以直接结束循环 
(存在极端情况导致答案错误)
另外,根据两点间距离公式 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msqrt><mrow><mo stretchy="false">(</mo><msub><mi>x</mi><mn>1</mn></msub><mo>−</mo><msub><mi>x</mi><mn>2</mn></msub><msup><mo stretchy="false">)</mo><mn>2</mn></msup><mo>+</mo><mo stretchy="false">(</mo><msub><mi>y</mi><mn>1</mn></msub><mo>−</mo><msub><mi>y</mi><mn>2</mn></msub><msup><mo stretchy="false">)</mo><mn>2</mn></msup></mrow></msqrt></mrow><annotation encoding="application/x-tex">\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}</annotation></semantics></math>(x1​−x2​)2+(y1​−y2​)2<svg width='400em' height='1.28em' viewBox='0 0 400000 1296' preserveAspectRatio='xMinYMin slice'><path d='M263,681c0.7,0,18,39.7,52,119
c34,79.3,68.167,158.7,102.5,238c34.3,79.3,51.8,119.3,52.5,120
c340,-704.7,510.7,-1060.3,512,-1067
l0 -0
c4.7,-7.3,11,-11,19,-11
H40000v40H1012.3
s-271.3,567,-271.3,567c-38.7,80.7,-84,175,-136,283c-52,108,-89.167,185.3,-111.5,232
c-22.3,46.7,-33.8,70.3,-34.5,71c-4.7,4.7,-12.3,7,-23,7s-12,-1,-12,-1
s-109,-253,-109,-253c-72.7,-168,-109.3,-252,-110,-252c-10.7,8,-22,16.7,-34,26
c-22,17.3,-33.3,26,-34,26s-26,-26,-26,-26s76,-59,76,-59s76,-60,76,-60z
M1001 80h400000v40h-400000z'/></svg>​ 
可以发现有一个非常浪费时间的 <code>sqrt()</code> 需要多次运算,可以在前面比较的时候直接比较距离的平方 
只要在最后输出的时候求一下平方就行 
(需要注意,如果这里比较距离的平方,上面遍历需要比较 <code>(x1-x2)^2</code>)
<h1 id="heading-2">代码</h1>
{% fold 点击显/隐代码 %}```cpp 平面上最近点对 <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份 
/// 
#define debug 
#include <ctime> 
/// 
#include <cstdio> 
#include <cstring>
#include <algorithm> 
#include <cmath> 
#include <iostream> 
using namespace std;
const int maxn = 60005; 
const double INF = 9e9; 
const int K = 5;
struct Point { 
int x, y; 
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {} 
bool operator&lt;(const Point &amp;rhs) const { return x &lt; rhs.x; } 
}; 
Point point[maxn];
inline double pow(double a, double n) { 
if (n == 0) 
return 1.0; 
if (n == 1) 
return a; 
return pow(a, n / 2) * pow(a, n - n / 2); 
}
inline double dis(Point a, Point b) { 
return pow(a.x - b.x, 2) + pow(a.y - b.y, 2); 
}
//[l,r) 
double dfs(int l, int r) { 
int mid = (l + r) / 2;
<pre><code>if (r - l &lt; 2) {
 return INF;
}
if (r - l == 2) {
 return dis(point[l], point[l + 1]);
}

double mm = min(dfs(l, mid), dfs(mid, r));

for (int i = mid - 1; i &gt;= l &amp;&amp; pow(point[mid].x - point[i].x,2) &lt; mm; i--)
 for (int j = mid; j &lt; r &amp;&amp; pow(point[r].x - point[mid-1].x,2) &lt; mm; j++)
 mm = min(mm, dis(point[i], point[j]));

return mm;
</code></pre>
}
int main() { 
#ifdef debug 
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin); 
int START = clock(); 
#endif 
cin.tie(0); 
cin.sync_with_stdio(false);
<pre><code>int n;
scanf(&quot;%d&quot;, &amp;n);
for (int i = 0; i &lt; n; i++)
 scanf(&quot;%d%d&quot;, &amp;point[i].x, &amp;point[i].y);

sort(point, point + n);
printf(&quot;%.4f\n&quot;, sqrt(dfs(0, n)));
</code></pre>
#ifdef debug 
printf(&quot;Time:%.3fs.\n&quot;, double(clock() - START) / CLOCKS_PER_SEC); 
#endif 
return 0; 
}
<pre style="background-color:#fff">{% endfold %}</pre>

AOJ 862.平面上最近点对