思维+数学

发表于2021-10-21更新于2021-10-21阅读次数

Sky Garden

题意，给n < 500个以原点为圆心的等间距圆，被m < 500条过圆心的直线均分，其中圆和直线以及直线和直线的交点构成了一个点集，问点集内的两两最短距离的和是多少（其中最短距离只能是从直线或圆上走出来的）。

·
·
·
·
·
··
·
·
·
··

··
·
·
·
·
·
·
·
·
·

··
·
·
·

思路：
不难证明和发现，从a到b，要么走线段+圆弧，要么就是两个线段。
然后这道题就可以暴力莽过去了。
也可以优化到n方。
对于一个圆，分点在圆上和在圆内考虑。
踩坑：这道都是浮点数的题，一个浮点数公式，写了a/2 * b * c，a为整形，b,c为浮点型，发生了整形截断，错了。

这道题让我知道，若求和可以用公式化简，就可以不用循环求和，优化复杂度。
还有就是这道题，O(1),O(n),O(n方)的运行时间几乎都没有区别。

n方做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
* @Author: Marhoosh
* @Date:   2021-10-11 11:00:11
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-21 16:52:25
*/
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
const ld pi=acos(-1);
ll n,m;
void solve(){
    ld ans=0;
    if(m==1){
        ans=1.0/6.0*(2*n+2)*(2*n+1)*(2*n)-n*(n+1);//此处推公式可以用到裂项相消法
        printf("%.10Lf\n",ans);
        return ;
    }
    for(ld r2=1;r2<=n;r2++){
        //圆内:
        ld ans1=0;
        for(ld i=1;i<=m-1;i++){
            if(i*pi*r2/m<2*r2){
                ans1=ans1+r2*(r2-1.0)/2.0*(i*pi/m+1);
            }
            else{
                ans1=ans1+3*r2/2.0*(r2-1);// /2出错
            }
        }  
        ans1=ans1*2;
        ans1=ans1+r2*(2*r2-1);
        ans1=ans1*2*m;
        ans+=ans1;
        //圆上：
        ld ans2=0;
        for(ld i=1;i<=m-1;i++){
            ans2+=min(i*pi*r2/m,(ld)2*r2);
        }
        ans2=ans2*2+2*r2;
        ans=ans+ans2*2*m/2.0;
    }
    printf("%.10Lf\n",ans);
}
int main(){
    cin>>n>>m;
    solve();
    return 0;
}

O(n) 做法：
/*

  • @Author: Marhoosh

  • @Date: 2021-10-11 11:00:11

  • @Last Modified by: Marhoosh

  • @Last Modified time: 2021-10-21 18:07:32

  • /
    #include<bits/stdc++.h>
    using namespace std;
    #define Debug(x) cout<<#x<<’:’<<x<<endl
    #define INF 0x7fffffff
    typedef long long ll;
    typedef long double ld;
    typedef pair<ll,ll> P;
    const ll maxn=2e5+11;
    const ld pi=acos(-1);
    ld n,m;
    void solve(){
    ld ans=0;
    if(m==1){

       ans=1.0/6.0*(2*n+2)*(2*n+1)*(2*n)-n*(n+1);
   printf("%.10Lf\n",ans);
   return ;

    }
    ld ans1=0,ans2=0;
    for(ld i=1;i<=m-1;i++){

       if(i*pi/m<2){
       ans1=ans1+1.0/6.0*(n+1)*n*(n-1)*(i*pi/m+1);
       ans2=ans2+i*pi/m;
   }
   else{
       ans1=ans1+1.0/2.0*(n+1)*n*(n-1);
       ans2=ans2+2.0;
   }

    }
    ans1*=2;
    ans1=ans1+n*(n+1)(4n-1)/6.0;
    ans=ans+ans12m;

    ans2=ans22+2;
    ans2    =m;
    ans=ans+ans2n(n+1.0)/2.0;

// for(ld r2=1;r2<=n;r2++){
//     //圆内:
//     ld ans1=0;
//     for(ld i=1;i<=m-1;i++){
//         if(i*pi*r2/m<2*r2){
//             ans1=ans1+r2*(r2-1.0)/2.0*(i*pi/m+1);
//         }
//         else{
//             ans1=ans1+3*r2/2.0*(r2-1);// /2出错
//         }
//     }  
//     ans1=ans1*2;
//     ans1=ans1+r2*(2*r2-1);
//     ans1=ans1*2*m;
//     ans+=ans1;
//     //圆上：
//     ld ans2=0;
//     for(ld i=1;i<=m-1;i++){
//         ans2+=min(i*pi*r2/m,(ld)2*r2);
//     }
//     ans2=ans2*2+2*r2;
//     ans=ans+ans2*2*m/2.0;
// }
printf("%.10Lf\n",ans);

}
int main(){
cin>>n>>m;
solve();
return 0;
}

O(1)做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
* @Author: Marhoosh
* @Date:   2021-10-11 11:00:11
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-21 18:25:51
*/
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
const ld pi=acos(-1);
ld n,m;
void solve(){
    ld ans=0;
    if(m==1){
        ans=1.0/6.0*(2*n+2)*(2*n+1)*(2*n)-n*(n+1);
        printf("%.10Lf\n",ans);
        return ;
    }
    ld ans1=0,ans2=0;
    ld x=floor(2.0*m/pi),y=ceil(2.0*m/pi);
    ans1=((1.0+x)*x/2.0*pi/m+x)*(n+1)*n*(n-1)/6.0;
    ans1=ans1+1.0/2.0*(n+1)*n*(n-1)*(m-1-y+1.0);

    ans2=(1.0+x)*x/2.0*pi/m;
    ans2=ans2+2.0*(m-1-y+1.0);

    // for(ld i=1;i<=m-1;i++){
    //     if(i*pi/m<2){
    //         ans1=ans1+1.0/6.0*(n+1)*n*(n-1)*(i*pi/m+1);
    //         ans2=ans2+i*pi/m;
    //     }
    //     else{
    //         ans1=ans1+1.0/2.0*(n+1)*n*(n-1);
    //         ans2=ans2+2.0;
    //     }
    // }
    ans1*=2;
    ans1=ans1+n*(n+1)*(4*n-1)/6.0;
    ans=ans+ans1*2*m;

    ans2=ans2*2+2;
    ans2*=m;
    ans=ans+ans2*n*(n+1.0)/2.0;


    // for(ld r2=1;r2<=n;r2++){
    //     //圆内:
    //     ld ans1=0;
    //     for(ld i=1;i<=m-1;i++){
    //         if(i*pi*r2/m<2*r2){
    //             ans1=ans1+r2*(r2-1.0)/2.0*(i*pi/m+1);
    //         }
    //         else{
    //             ans1=ans1+3*r2/2.0*(r2-1);// /2出错
    //         }
    //     }  
    //     ans1=ans1*2;
    //     ans1=ans1+r2*(2*r2-1);
    //     ans1=ans1*2*m;
    //     ans+=ans1;
    //     //圆上：
    //     ld ans2=0;
    //     for(ld i=1;i<=m-1;i++){
    //         ans2+=min(i*pi*r2/m,(ld)2*r2);
    //     }
    //     ans2=ans2*2+2*r2;
    //     ans=ans+ans2*2*m/2.0;
    // }
    printf("%.10Lf\n",ans);
}
int main(){
    cin>>n>>m;
    solve();
    return 0;
}