排序以后做O(n^2)的枚举

因为排过序所以……（此处省略部分自己想 反正加上这个就AC否则就TLE）

终于过了~~~~~~~~

因为这道题浪费我20多次提交次数*~*

不是很懂
O(n^2)=1e10 时间5s 评测机O2 暴力剪枝
凭什么看不起理论实践都能过的暴力？

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
template<class T> inline void read(T &_a){
    bool f=0;int _ch=getchar();_a=0;
    while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
    while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}
    if(f)_a=-_a;
}

struct fff{
    long long x,y;
    inline bool operator < (const fff xx) const { return x<xx.x; }
}node[100001];
long long ans=1e14,n;

int main()
{
    read(n);
    for (register int i=1;i<=n;++i) read(node[i].x),read(node[i].y);
    sort(node+1,node+n+1);
    for (register int i=1;i<n;++i)
     for (register int v=i+1;v<=n;++v)
      if((node[v].x-node[i].x)*(node[v].x-node[i].x)<ans)
       ans=min(ans,(node[i].x-node[v].x)*(node[i].x-node[v].x)+(node[i].y-node[v].y)*(node[i].y-node[v].y));
        else break;
    printf("%.3lf",sqrt((double)ans));
    return 0;
} 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double inf=double(1e100);
inline const void read(double &a)//快读
{
a=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=a*10+c-'0';
c=getchar();
}
}
class point//点的各个元素
{
public:
int num;//这个点的编号，好像最后没用
double x,y;
bool operator<(const point b)//重载运算<,以x为第一关键字，y为第二关键字
{
if(x<b.x)return true;
if(x>b.x)return false;
if(y<=b.y)return true;
else return false;
}
}p[100001];
int n;
inline const double min_double(double a,double b)//double型的比较函数
{
if(a<b)return a;
else return b;
}
inline const double dis(int a,int b)//算两点间的距离
{
return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
}
inline const bool compare(point a,point b)
{
if(a<b)return true;
else return false;
}
double dp(int l,int r)//左右区间，l与r是编号
{
if(l==r-1)return dis(l,r);//只有两个点，最短距离一定为这对点
if(l==r)return inf; //只有一个点，最短距离不存在
int mid=(l+r)/2,mid_x=p[mid].x;//中间位置 中间位置的横坐标
double len=min_double(dp(l,mid),dp(mid,r));//合并两个分区间后的最小点对值
for(int i=mid;i>=l;i--)
{
if(p[i].x<mid_x-len)break;//这里就是暴力的剪枝，如果x轴之差已经大于len，直接减枝
for(int j=mid+1;j<=r;j++)
{
if(p[j].x>mid_x+len)break;//同上
len=min_double(len,dis(i,j));
}
}
return len;//返回本区间最优
}
int main()
{
//freopen("测试数据.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
read(p[i].x);read(p[i].y);
p[i].num=i;
}
sort(p+1,p+n,compare);
double ans=dp(1,n);
printf("%.3lf",ans);
return 0;
}
数据不是很强，其实所谓的分治不过就是暴力，多一个合并时的剪枝。
此题数据不是很好，让没有优化的暴力也通的过。

这数据怎么有小数。、。难怪我过不了！！！！
很简单的排序+枚举，Pascal也过了。。
PS:我用C++死活TLE，过一个点，用的还是sort。。

http://www.cnblogs.com/oierforever/p/4764152.html

用C语言printf("%.3f",doubleType);
不要lf.坑爹无比.
--------------------%%------------------
----------%%--------%%------------------
----------%%%--------%%-----------------
-----------%%%--------%%%---------------
-----------%%---------%%%---------------
-----------%%----------%%%--------------
-----------%%----------%%%--------------
-----------%%-----------%%--------------
-----------%%-----------%%--------------
-----------%%-------------------%%------
-----------%%---------------%%%%%%%-----
-----------%%---------%%%%%%%%%%%%%%----
-----------%%--%%%%%%%%%%%%%------------
-----------%%---%%%%%%%-----------------
-----------%%---------------------------
-----------%%--%%-----------------------
-----------%%%%%%--%%-----%%------------
--------%%%%%%%%%%-%%-----%%%-----------
-----%%%%%%%%%-----%%--%%%%%%-----------
------%%---%%------%%%%%%%%%------------
-----------%%------%%%----%%------------
-----------%%------%%%----%%------------
-----------%%------%%%----%%------------
-----------%%------%%%----%%------------
-----------%%------%%%----%%------------
-----------%%------%%-----%%------------
-----------%%------%%-----%%------------
-----------%%---%%-%%-----%%------------
-----------%%-%%%--%%-----%%------------
-----------%%%%%---%%-----%%------------
----------%%%%----%%%-----%%------%-----
--------%%%%------%%------%%------%-----
------%%%%%-------%%------%%------%-----
----%%%%%---------%%------%%------%-----
----%%%%---------%%%------%%------%%----
-----%%----------%%-------%%------%%----
----------------%%%-------%%------%%----
----------------%%--------%%------%%----
---------------%%---------%%------%%----
--------------%%%---------%%%----%%%----
--------------%%----------%%%%-%%%%%%---
------------%%%-------------%%%%%%%-----
-----------%%%--------------------------
-----------%----------------------------

nlogn。。非暴力正解
正解原来是分治.....
学习了
http://blog.csdn.net/lytning/article/details/25370169

Free Pascal Compiler version 2.6.2 [2013/02/12] for i386
Copyright (c) 1993-2012 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(31,5) Note: Local variable "p" not used
foo.pas(31,7) Note: Local variable "q" not used
Linking foo.exe
56 lines compiled, 0.1 sec , 33824 bytes code, 1804 bytes data
2 note(s) issued
*测试数据 #0: Accepted, time = 93 ms, mem = 2180 KiB, score = 10
*测试数据 #1: Accepted, time = 156 ms, mem = 2184 KiB, score = 10
*测试数据 #2: Accepted, time = 93 ms, mem = 2184 KiB, score = 10
*测试数据 #3: Accepted, time = 15 ms, mem = 2180 KiB, score = 10
*测试数据 #4: Accepted, time = 109 ms, mem = 2184 KiB, score = 10
*测试数据 #5: Accepted, time = 62 ms, mem = 2180 KiB, score = 10
*测试数据 #6: Accepted, time = 109 ms, mem = 2180 KiB, score = 10
*测试数据 #7: Accepted, time = 124 ms, mem = 2184 KiB, score = 10
*测试数据 #8: Accepted, time = 46 ms, mem = 2184 KiB, score = 10
*测试数据 #9: Accepted, time = 140 ms, mem = 2184 KiB, score = 10
*Accepted, time = 947 ms, mem = 2184 KiB, score = 100

var x,y:array[0..100010]of double;
n:longint;
procedure init;
var i:longint;
begin
readln(n);
for i:=1 to n do
readln(x[i],y[i]);
end;
procedure kp(st,ed:longint);
var i,j:longint;
q,t:double;
begin
i:=st;
j:=ed;
q:=x[(i+j)div 2];
repeat
while x[i]<q do inc(i);
while x[j]>q do dec(j);
if i<=j then
begin
t:=x[i];x[i]:=x[j];x[j]:=t;
t:=y[i];y[i]:=y[j];y[j]:=t;
inc(i);dec(j);
end;
until i>j;
if st<j then kp(st,j);
if i<ed then kp(i,ed);
end;
function dis(i,j:longint):double;
var p,q:int64;
begin
dis:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
end;
procedure main;
var min,l:double;
i,j,k:longint;
begin
kp(1,n);
min:=1e10;
for i:=1 to n do
begin
j:=i+1;
while (x[j]-x[i]<min)and(j<=n) do inc(j);
for k:=i+1 to j-1 do
begin
l:=dis(i,k);
if min>l then min:=l;
end;
end;
writeln(min:0:3);
end;
begin
init;
main;
end.

Free Pascal Compiler version 2.6.2 [2013/02/12] for i386
Copyright (c) 1993-2012 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(31,5) Note: Local variable "p" not used
foo.pas(31,7) Note: Local variable "q" not used
Linking foo.exe
56 lines compiled, 0.1 sec , 33824 bytes code, 1804 bytes data
2 note(s) issued
测试数据 #0: Accepted, time = 93 ms, mem = 2180 KiB, score = 10
测试数据 #1: Accepted, time = 156 ms, mem = 2184 KiB, score = 10
测试数据 #2: Accepted, time = 93 ms, mem = 2184 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 2180 KiB, score = 10
测试数据 #4: Accepted, time = 109 ms, mem = 2184 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 2180 KiB, score = 10
测试数据 #6: Accepted, time = 109 ms, mem = 2180 KiB, score = 10
测试数据 #7: Accepted, time = 124 ms, mem = 2184 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 2184 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 2184 KiB, score = 10
Accepted, time = 947 ms, mem = 2184 KiB, score = 100

var x,y:array[0..100010]of double;
n:longint;
procedure init;
var i:longint;
begin
readln(n);
for i:=1 to n do
readln(x[i],y[i]);
end;
procedure kp(st,ed:longint);
var i,j:longint;
q,t:double;
begin
i:=st;
j:=ed;
q:=x[(i+j)div 2];
repeat
while x[i]<q do inc(i);
while x[j]>q do dec(j);
if i<=j then
begin
t:=x[i];x[i]:=x[j];x[j]:=t;
t:=y[i];y[i]:=y[j];y[j]:=t;
inc(i);dec(j);
end;
until i>j;
if st<j then kp(st,j);
if i<ed then kp(i,ed);
end;
function dis(i,j:longint):double;
var p,q:int64;
begin
dis:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
end;
procedure main;
var min,l:double;
i,j,k:longint;
begin
kp(1,n);
min:=1e10;
for i:=1 to n do
begin
j:=i+1;
while (x[j]-x[i]<min)and(j<=n) do inc(j);
for k:=i+1 to j-1 do
begin
l:=dis(i,k);
if min>l then min:=l;
end;
end;
writeln(min:0:3);
end;
begin
init;
main;
end.

测试数据 #0: Accepted, time = 140 ms, mem = 2000 KiB, score = 10
测试数据 #1: Accepted, time = 171 ms, mem = 2000 KiB, score = 10
测试数据 #2: Accepted, time = 124 ms, mem = 2004 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 1996 KiB, score = 10
测试数据 #4: Accepted, time = 171 ms, mem = 2000 KiB, score = 10
测试数据 #5: Accepted, time = 93 ms, mem = 2000 KiB, score = 10
测试数据 #6: Accepted, time = 202 ms, mem = 2000 KiB, score = 10
测试数据 #7: Accepted, time = 187 ms, mem = 2004 KiB, score = 10
测试数据 #8: Accepted, time = 93 ms, mem = 1996 KiB, score = 10
测试数据 #9: Accepted, time = 187 ms, mem = 2000 KiB, score = 10
Accepted, time = 1399 ms, mem = 2004 KiB, score = 100

...好丑的时间...
个人觉得排序+暴搜+剪枝（横坐标之差<min时去掉）就OK了

题解

测试数据 #0: Accepted, time = 109 ms, mem = 2692 KiB, score = 10

测试数据 #1: Accepted, time = 109 ms, mem = 2692 KiB, score = 10

测试数据 #2: Accepted, time = 62 ms, mem = 2692 KiB, score = 10

测试数据 #3: Accepted, time = 46 ms, mem = 2688 KiB, score = 10

测试数据 #4: Accepted, time = 125 ms, mem = 2692 KiB, score = 10

测试数据 #5: Accepted, time = 78 ms, mem = 2688 KiB, score = 10

测试数据 #6: Accepted, time = 78 ms, mem = 2688 KiB, score = 10

测试数据 #7: Accepted, time = 62 ms, mem = 2696 KiB, score = 10

测试数据 #8: Accepted, time = 31 ms, mem = 2688 KiB, score = 10

测试数据 #9: Accepted, time = 62 ms, mem = 2692 KiB, score = 10

Accepted, time = 762 ms, mem = 2696 KiB, score = 100

0 0

交了将近10次才发现自己快排了X忘记一起交换Y……感觉好二

测试数据 #0: Accepted, time = 109 ms, mem = 2772 KiB, score = 10
测试数据 #1: Accepted, time = 140 ms, mem = 2768 KiB, score = 10
测试数据 #2: Accepted, time = 109 ms, mem = 2768 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 2768 KiB, score = 10
测试数据 #4: Accepted, time = 125 ms, mem = 2768 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 2768 KiB, score = 10
测试数据 #6: Accepted, time = 125 ms, mem = 2772 KiB, score = 10
测试数据 #7: WrongAnswer, time = 109 ms, mem = 2768 KiB, score = 0
测试数据 #8: Accepted, time = 62 ms, mem = 2768 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 2768 KiB, score = 10
我该怎么拯救自己的分治.....

请帝系列通关,纪念下.....

题解

点击查看程序源码+详细题解

二分过不了blacksnow的数据。-_-。。。

大概是编错了求正解

汗。。

分治的一个不等号打反了都能90.。。

這道題目能夠過完全是因爲數據弱，你可以試試下面這組數據...

同志們，考慮更高效的算法吧。

http://www.oibh.org/bbs/thread-34087-1-1.html

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms