# 分治法

HDU 1007 Quoit Design

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100000 + 10, Mod = 1000000000;
typedef long long ll;
typedef pair<double, double> P;
P p[N], q[N];
double dis(P a, P b)
{
return sqrt((a.first - b.first)*(a.first - b.first) +
(a.second - b.second)*(a.second - b.second));
}
int cmp(P a, P b)
{
return a.second < b.second;
}
double solve(int l, int r)
{
if(l == r) return inf;
if(r - l == 1) return dis(p[l], p[r]);
int mid = (l+r)>>1, c = 0;
double x = p[mid].first;
double d = min(solve(l, mid), solve(mid+1, r));
for(int i = l; i<=r; i++)
{
if(fabs(p[i].first - x) <= d)
q[c++] = p[i];
}
sort(q, q+c, cmp);
for(int i = 0; i<c; i++)
{
for(int j = i+1; j<c && q[j].second - q[i].second<d; j++)
{
double li = dis(q[j], q[i]);
d = min(d, li);
}
}
return d;
}
int main()
{
int n;
while(~scanf("%d", &n) && n)
{
for(int i = 0; i<n; i++)
scanf("%lf%lf", &p[i].first, &p[i].second);
sort(p, p+n);
printf("%.2f\n", solve(0, n-1)/2);
}
return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100000 + 10, Mod = 1000000000;
typedef long long ll;
typedef pair<double, double> P;
typedef vector<int> V;
V a;
ll solve(V &amp;a)
{
ll cnt = 0;
int n = a.size();
if(n<=1) return 0;
V b(a.begin(), a.begin() + n/2);
V c(a.begin() + n/2, a.end());
cnt += solve(b);
cnt += solve(c);
int ai = 0, bi = 0, ci = 0;
while(ai<n)
{
if(bi<b.size() &amp;&amp; (ci == c.size() || b[bi] <= c[ci]))
a[ai++] = b[bi++];
else
{
a[ai++] = c[ci++];
cnt += n/2 - bi;
}
}
return cnt;
}
int main()
{
int n, x;
while(~scanf("%d", &amp;n) &amp;&amp; n)
{
a.clear();
for(int i = 0; i<n; i++)
scanf("%d", &amp;x), a.push_back(x);
printf("%lld\n", solve(a));
}
return 0;
}