题目链接: https://vjudge.net/problem/POJ-3714
题意: 给定两个点集, 求最短距离.
思路: 在平面最近点对基础上加了个条件, 我么不访用 f 做标记, 集合 1 的 f 为 1, 集合 2 的 f 为 - 1, 那么求两个点的距离时, 如果 a.f*b.f=-1 时计算距离, 否则乘积为 1 的话返回 inf. 其它就和 hdoj1007 一样了.
AC 代码:
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- #include<cstdlib>
- using namespace std;
- const int maxn=2e5+5;
- const double inf=1e30;
- int T,n,cnt,id[maxn];
- struct node{
- int x,y,f;
- }pt[maxn];
- bool operator <(const node& a,const node& b){
- if(a.x==b.x) return a.y<b.y;
- return a.x<b.x;
- }
- bool cmp(int a,int b){
- return pt[a].y<pt[b].y;
- }
- double dist(const node& a,const node& b){
- if(a.f*b.f==1) return inf;
- return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
- }
- double fenzhi(int l,int r){
- double d=inf;
- if(l==r) return d;
- if(l+1==r) return dist(pt[l],pt[r]);
- int mid=(l+r)>>1;
- d=min(fenzhi(l,mid),fenzhi(mid+1,r));
- cnt=0;
- int t1,t2,l1=l,r1=mid,mid1;
- while(l1<=r1){
- mid1=(l1+r1)>>1;
- if(pt[mid].x-pt[mid1].x<d) r1=mid1-1;
- else l1=mid1+1;
- }
- t1=l1;
- l1=mid+1,r1=r;
- while(l1<=r1){
- mid1=(l1+r1)>>1;
- if(pt[mid1].x-pt[mid].x<d) l1=mid1+1;
- else r1=mid1-1;
- }
- t2=r1;
- for(int i=t1;i<=t2;++i)
- id[++cnt]=i;
- sort(id+1,id+cnt+1,cmp);
- for(int i=1;i<cnt;++i)
- for(int j=i+1;j<=cnt&&(pt[id[j]].y-pt[id[i]].y<d);++j)
- d=min(d,dist(pt[id[i]],pt[id[j]]));
- return d;
- }
- int main(){
- scanf("%d",&T);
- while(T--){
- scanf("%d",&n);
- for(int i=1;i<=2*n;++i){
- scanf("%d%d",&pt[i].x,&pt[i].y);
- if(i<=n) pt[i].f=1;
- else pt[i].f=-1;
- }
- sort(pt+1,pt+1+2*n);
- printf("%.3f\n",fenzhi(1,2*n));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3170663.html