模板题,改一改就a了,注意输出格式
#include<iostream> #include<algorithm> #include<vector> #include<cmath> using namespace std; struct point{ double x,y; int f; point():x(0),y(0),f(0){} }; vector<point> p; vector<int> a; int n; double dis(point a,point b){ if(a.f != b.f) return sqrt(pow(a.x-b.x,2)+pow(a.y - b.y,2)); return 0x3f3f3f3f; } bool cmp1(point a,point b){ if (a.x != b.x)return a.x < b.x; return a.y < b.y; } double near_dis(int l,int r){ if(r == l + 1) return dis(p[l],p[r]); if(l + 2 == r) return min(dis(p[l],p[r]),min(dis(p[l],p[l+1]),dis(p[l+1],p[r]))); int mid =( l + r) >> 1; double ans = min(near_dis(l,mid),near_dis(mid+1,r)); a.clear(); for(int i = l;i <= r;i++) if(p[i].x >= p[mid].x - ans && p[i].x <= p[mid].x + ans) a.push_back(i); for(int i = 0;i < a.size();i++){ for(int j = i + 1;j<a.size();j++){ if(abs(p[a[j]].y - p[a[i]].y) >= ans) break; ans = min(ans ,dis( p[a[i]],p[a[j]])); } } return ans; } int main(){ int t;cin>>t; while(t--){ cin>>n; p.resize(2 * n + 1); for(int i = 1;i < p.size();i++) { cin>>p[i].x>>p[i].y; if(i <= n) p[i].f = 1; } sort(p.begin()+1,p.end(),cmp1); printf("%.3f\n",near_dis(1,2*n)); } return 0; }