平面上的最接近点对

2014年8月20日3,4510

http://218.5.5.242:9018/JudgeOnline/problem.php?id=1431

题目描述

给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的。

输入

第一行：n；2≤n≤60000 接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。

输出

仅一行，一个实数，表示最短距离，精确到小数点后面4位。

题解

随机分块可水

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<cstdlib>
#define inf 1000000000
#define linf 90000000000LL
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,block,cnt;
double ans=1e60;
struct P{double x,y;}p[60005];
double dis(P a,P b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool operator <(P a,P b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
P rotate(P a,double x)
{
    return (P){a.x*cos(x)-a.y*sin(x),a.y*cos(x)+a.x*sin(x)};
}
void cal(int a,int b)
{
	for(int i=a;i<=b;i++)
		for(int j=i+1;j<=b;j++)
			ans=min(ans,dis(p[i],p[j]));
}
void solve()
{
	double t=rand()/10000;
	for(int i=1;i<=n;i++)
		p[i]=rotate(p[i],t);
	sort(p+1,p+n+1);
	for(int i=1;i<=cnt;i++)
	{
        int t1=block*(i-1)+1,t2=block*i;
        t2=min(t2,n);
        cal(t1,t2);
    }
}
int main()
{
	n=read();
    block=sqrt(n)+10;
    cnt=n/block+(n%block!=0);
    for(int i=1;i<=n;i++)
        p[i].x=read(),p[i].y=read();
    solve();
	printf("%.4lf",sqrt(ans));
	return 0;
}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

#include<map>

#include<cstdlib>

#define inf 1000000000

#define linf 90000000000LL

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,block,cnt;

double ans=1e60;

struct P{double x,y;}p[60005];

double dis(P a,P b)

{

return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

}

bool operator <(P a,P b)

{

return a.x<b.x||(a.x==b.x&&a.y<b.y);

}

P rotate(P a,double x)

{

return (P){a.x*cos(x)-a.y*sin(x),a.y*cos(x)+a.x*sin(x)};

}

void cal(int a,int b)

{

for(int i=a;i<=b;i++)

for(int j=i+1;j<=b;j++)

ans=min(ans,dis(p[i],p[j]));

}

void solve()

{

double t=rand()/10000;

for(int i=1;i<=n;i++)

p[i]=rotate(p[i],t);

sort(p+1,p+n+1);

for(int i=1;i<=cnt;i++)

{

int t1=block*(i-1)+1,t2=block*i;

t2=min(t2,n);

cal(t1,t2);

}

int main()

{

n=read();

block=sqrt(n)+10;

cnt=n/block+(n%block!=0);

for(int i=1;i<=n;i++)

p[i].x=read(),p[i].y=read();

solve();

printf("%.4lf",sqrt(ans));

return 0;

}

« 「BZOJ3632」外太空旅行「BZOJ3707」「FJ2014集训」圈地 »

hzwer.com _ Home | http://hzwer.com

平面上的最接近点对

题目描述

输入

输出

题解

分类目录

热门文章

Myfriends

近期评论