# 139 条题解

• @ 2021-05-06 17:10:01

#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define eps 1e-8
#define J 10000
#define MAX 0x7f7f7f7f
#define PI 3.1415926535897
#define N 100004
using namespace std;
int n,m,lll,ans,cas;
double b,c;
struct xxx
{
double x,y;
}a[N];
bool cmp(xxx aa,xxx bb)
{
if(aa.x!=bb.x)return aa.x<bb.x;
return aa.y<bb.y;
}
int main() {
int i,j,k;
while(~scanf("%d",&n) && n)
{
c=1000000000000;
for(i=1;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+1+n,cmp);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(sqr(a[i].x-a[j].x)>c)break;
b=sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y);
c=min(c,b);
}
}
c=sqrt(c);
printf("%.3lf\n",c);
}
return 0;
}

• @ 2018-11-29 22:50:54

简单的枚举和快排而已。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define sqr(x) x*x
using namespace std;

int n;
double ans;
struct lx
{
double x,y;
}p[100005];

bool cmp(lx a,lx b)
{
return (sqr(a.x)+sqr(a.y))<(sqr(b.x)+sqr(b.y));
}

int main()
{
while(~scanf("%d",&n))
{
for (int i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p+1,p+n+1,cmp);
ans=sqrt(sqr((p[n].x-p[1].x))+sqr((p[n].y-p[1].y)));
for (int i=1;i<=n;i++)
{
int k=i+1;
while (p[k].y-p[i].y<ans&&k<n) k++;
for (int j=i+1;j<=k;j++)
{
ans=min(ans,sqrt(sqr((p[j].x-p[i].x))+sqr((p[j].y-p[i].y))));
}
}
printf("%.3lf\n",ans);
}
}

• @ 2020-05-23 15:30:08

dgbcccmmmmmmm

• @ 2009-07-18 14:36:47

水题

准确说数据太弱

看红色部分，这是看RP的：

begin

Min:=999999999999999999;

For i:=1 to n do

qsort(1,n);

For i:=1 to n-1 do

For j:=i+1 to Mm(i+10,n) do

IF sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]))

• @ 2009-07-14 22:22:32

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

qsort+枚举就有如此效率

• @ 2009-07-11 23:22:21

额。当我没说。又看错题。。。

King465656你改成int64看看

• @ 2009-07-08 19:05:20

分治典型题。

一开始写了个快排，没有加到程序里，WA了两次还死命的查错，太囧了。

• @ 2009-07-08 16:25:57

有一个很囧很强大的问题

快排如果这样打

While XMid do Dec(J);

（Mid:=X[(I+J) Div 2];Mid:Extended）

就对了

但是如果是

While XX[Mid] do Dec(J);

(Mid:=(I+J)Div 2;Mid:Longint)

就全错。。。

这个是。。。什么问题

• @ 2009-05-12 22:08:26

分治法

procedure find(li,ri:longint);

var

i,j,m:longint;

d:double;

begin

if ri

• @ 2009-05-05 11:08:19

总的来说，数据弱的可以，puppy快的可以。

貌似都是随机数据。

离散化+下界判定(if (a[j,1]-a>min) then break;)

pascal，错误207的话，把保存点的数组定义为int64，因为2^32*2^32>maxlongint

• @ 2009-03-25 21:56:31

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

• @ 2009-03-18 15:56:21

快排,确定最优解范围+枚举

p:=1;

for i:=1 to n do

begin

p:=i+1;

while (x[p]-x[i]

• @ 2009-03-13 19:41:17
``````想起了RYH大牛以前山寨的《魔兽争霸》了~~~~~~~~~
``````
• @ 2009-02-23 21:37:20

PROGRAM JamesBend;

var

s:array[1..100000] of record

x:int64;

y:int64;

end;

w,min:real;

i,j,n:longint;

procedure change(a,b:int64);

var

c:int64;

begin

c:=s[a].x;

s[a].x:=s.x;

s.x:=c;

c:=s[a].y;

s[a].y:=s.y;

s.y:=c;

end;

function dis(a,b:int64):real;

begin

dis:=sqrt(sqr(s[a].x-s.x)+sqr(s.y-s[a].y));

end;

procedure quiksort(h,t:int64);

var

pivot,i,j:int64;

begin

if hs[i].x do inc(i);

while pivoth then quiksort(1,j);

if i)=min then break

else

begin

w:=dis(i,j);

if w

• @ 2009-01-31 12:13:48

编译通过...

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

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

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

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

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

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

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

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

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

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

这道题目只是想AC的就直接搜索剪枝。。。就是上面的。。。

正解貌似是分治。。不过编程复杂度大。。时间划不来。。

• @ 2009-01-24 14:01:39

其实....加一个最简单的剪枝就能过- -

时间很恐怖:

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

for(int i=1;i

• @ 2009-01-05 22:33:13

时间很丑。。。具体思想，先排序，然后分治。

详细的见这里：http://cai0715.wvpmx.com/?p=45

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

• @ 2008-12-19 22:37:35

break 打成了 continue …………… TEL了两次~！

细心那~！

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

• @ 2008-12-07 10:34:20

puppy 0ms

• @ 2008-11-12 20:52:31

一次AC,感谢Puppy

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

分治!!有学了点东西. ^-^

特贴上程序纪念一下

var

x,y:array[1..100000]of double;

i,j,k,p,n:longint;

procedure qsort(l,r: longint);

var

i,j: longint;

mid,t:double;

begin

i:=l; j:=r; mid:=x[(l+r) shr 1];

repeat

while x[i]j;

if l

ID
1012

7

4106

875

21%

12