竟RE了?

P1429 平面最近点对(加强版)

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

rt

求助


by 142857cs @ 2019-12-03 09:57:25

@starusc 话说是不是没有保证输入是整数啊,如果不是整数你这么读入就不对


by zmx_wzx_JY @ 2019-12-23 21:56:09

做灰题的大佬orz


|