只需要特判标记即可
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
const double eps = 1e-8;
const double inf = 9999999999.0;
const int maxn = 100005;
struct Point{
double x,y;
int flag;
};
Point pnt[ maxn<<1 ],temp[ maxn<<1 ];
double dis( Point a,Point b ){
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
int cmpxy( Point a,Point b ){
if( a.x!=b.x )
return a.x<b.x;
else
return a.y<b.y;
}
int cmpx( Point a,Point b ){
return a.x<b.x;
}
int cmpy( Point a,Point b ){
return a.y<b.y;
}
double solve( int L,int R ){
if( L==R )
return inf;
if( L+1==R ){
if( pnt[L].flag==pnt[R].flag )
return inf;
else
return dis( pnt[L],pnt[R] );
}
int mid = (L+R)/2;
double res,Ldis,Rdis;
Ldis = solve( L,mid );
Rdis = solve( mid+1,R );
res = min( Ldis,Rdis );
int cnt = 0;
for( int i=L;i<=R;i++ ){
if( fabs(pnt[i].x-pnt[mid].x)<=res ){
temp[cnt++] = pnt[i];
}
}
sort( temp,temp+cnt,cmpy );
for( int i=0;i<cnt;i++ ){
for( int j=i+1;j<cnt;j++ ){
if( fabs( pnt[i].y-pnt[j].y )>res ) break;
if( pnt[i].flag==pnt[j].flag ) continue;
res = min( res,dis(pnt[i],pnt[j]) );
}
}
return res;
}
int main(){
int ca;
scanf("%d",&ca);
while( ca-- ){
int n;
scanf("%d",&n);
for( int i=0;i<n;i++ ){
scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
pnt[i].flag = 1;
}
for( int i=n;i<2*n;i++ ){
scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
pnt[i].flag = 2;
}
sort( pnt,pnt+2*n,cmpxy );
double Ans = solve( 0,2*n-1 );
printf("%.3lf\n",Ans);
}
return 0;
}
分享到:
相关推荐
三道几何题:hdu 1007、hdu 2289、poj 3714
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
POJ 最接近点对问题 ACM北大 using namespace std; struct Point { float x; float y; };
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
北大POJ2002-Squares 解题报告+AC代码
北大POJ初级-简单搜索 解题报告+AC代码
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
西北工业大学POJ试题C++答案代码+课程设计
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友