hdu 2073：无限的路（思维）

快来打我* 2023-06-09 10:06 5阅读 0赞

# hdu 2073：无限的路（思维） #

[题目链接][Link 1]

开始想着用个前缀，然后后面直接调用即可，但是由于实力有限，没能搞出来，后面就想着干脆暴力模拟，结果交一发TLE。。。。。

于是就开始看大佬们的博客了

[https://blog.csdn.net/yangyafeiac/article/details/7828435][https_blog.csdn.net_yangyafeiac_article_details_7828435]

居然又是一道思维题，感觉还是比较难想到，其实我觉得前缀其实可以的，但是就是没弄出来

![20191020004237584.png][]

有点迷…

**AC代码：**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<cmath>
    using namespace std;
    double fx(int x,int y){
        
        double ans=0.0;
        double m=sqrt(2.0);
        int n=x+y;
        for(int i=1;i<n;i++){
        
            ans+=i*m*1.0;
        }
        ans+=x*m;           //这里重点注意
        for(int i=0;i<n;i++)
            ans+=sqrt(i*i*1.0+(i+1)*(i+1)*1.0);
        return ans;
    }
    int main(){
        
        int t;
        int x1,y1,x2,y2;
        scanf("%d",&t);
        while(t--){
        
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            printf("%.3f\n",fabs(fx(x1,y1)-fx(x2,y2)));
        }
        return 0;
    }

**TLE代码：**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<cmath>
    #define ll long long
    using namespace std;
    int main(){
        
        int k;
        int x1,y1,x2,y2;
        scanf("%d",&k);
        while(k--){
        
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if((x1+y1)>=(x2+y2)){
        
                int t=x1;
                x1=x2;
                x2=t;
                t=y1;
                y1=y2;
                y2=t;
            }
            int i=x1,j=y1;
            double sum=0.0;
            while(!(i==x2&&j==y2)){
        
                if(i==0&&j==0){
        
                    sum+=1.0;
                    j++;
                }
                else if(j==0){
        
                    sum+=sqrt(i*i*1.0+(i+1)*(i+1)*1.0);
                    j=i+1;
                    i=0;
                }
                else{
        
                    sum+=sqrt(2.0);
                    i++;
                    j--;
                }
            }
            printf("%.3f\n",sum);
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2073
[https_blog.csdn.net_yangyafeiac_article_details_7828435]: https://blog.csdn.net/yangyafeiac/article/details/7828435
[20191020004237584.png]: /images/20230531/27b75bb0294a42ba9de43bf79729dfcb.png