starusc @ 2019-12-03 08:07:13
这道题过了,但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);
}
by starusc @ 2019-12-03 08:07:36
求助
by 142857cs @ 2019-12-03 09:57:25
@starusc 话说是不是没有保证输入是整数啊,如果不是整数你这么读入就不对
by zmx_wzx_JY @ 2019-12-23 21:56:09
做灰题的大佬orz