@starusc 2019-12-03 08:07 回复 这道题过了,但UVA上的多组数据RE了,调大数组后显示TLE,不知所措的蒟蒻求助 题目链接 //starusc #include<bits/stdc++.h> using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f==1?x:-x; } const int N=1e4+4; double mnds; struct node{ int x,y; }a[N],t[N]; int n; inline bool comp_x(const node &x,const node &y){ return x.x==y.x?x.y<y.y:x.x<y.x; } inline bool comp_y(const node &x,const node &y){ return x.y==y.y?x.x<y.x:x.y<y.y; } inline double sqr(int x){ return (double)x*x; } #define min_(a,b) (a>b?b:a) inline void update(node x,node y){ mnds=min_(mnds,sqrt(sqr(x.x-y.x)+sqr(x.y-y.y))); } inline void solve(int l,int r){ if(r-l<=3){ for(int i=l;i<=r;i++) for(int j=i+1;j<=r;j++) update(a[i],a[j]); sort(a+l,a+r+1,comp_y); return; } int mid=l+r>>1,mdx=a[mid].x; solve(l,mid);solve(mid+1,r); merge(a+l,a+mid+1,a+mid+1,a+r+1,t,comp_y); copy(t,t+r-l+1,a+l); for(int i=l,trz=0;i<=r;i++){ if(abs(a[i].x-mdx)<mnds){ for(int j=trz;j>0&&a[i].y-t[j].y<mnds;j--) update(a[i],t[j]); t[++trz]=a[i]; } } } int main(){ while(1){ n=read(); if(!n)return (0-0); for(int i=1;i<=n;i++){ a[i].x=read();a[i].y=read(); } sort(a+1,a+n+1,comp_x); mnds=10000; solve(1,n); if(mnds==10000)cout<<"INFINITY"<<"\n"; else printf("%.4lf\n",mnds); } return (0-0); }
这道题过了,但UVA上的多组数据RE了,调大数组后显示TLE,不知所措的蒟蒻求助
题目链接