Moscow Subregional 2010 Problem A. Alien Visit 计算几何、连续圆的总面积

ACM ICPC 2010-2011 NEERC Moscow Subregional Contest Moscow, October 24, 2010

Problem A. Alien Visit 计算几何、连续圆的总面积

Source

Moscow Subregional 2010

My Solution

计算几何 计算 一串可能有相交可能有相离的同半径且圆心在同一水平面的圆的总面积

总共是分三类讨论

1、相交， 圆心相距比较远， 相交并且 相交部分在那个菱形里面

2、相交， 圆心相距比较近， 那个菱形在相交部分里面

3、相离， 外离

注意一下精度

然后就是 每次把相交部分算到前一个圆， 然后一次算去就好了

Wrong answer， 然后对圆心排个序就通过了， 本来以为默认就是升序的， 结果是乱序的⊙﹏⊙‖∣

复杂度 O(n)

这个是队友代码实现的， 所以向队友 nardo 要了AC代码

#include<bits/stdc++.h>
using namespace std;

const double pi = acos(-1);
int n;
double r,x,pre,ans = 0.0;
double centers[10000];

int main(){
    cin >> n >> r;
    for(int i = 1;i <= n;++i) cin >> centers[i];
    sort(centers + 1,centers + 1 + n);
    pre = -1e9;
    for(int i = 1;i <= n;++i){ x = centers[i]; if(x > pre + 2 * r){
            ans += pi * r * r;
        }
        else{
            double dd = x - pre;
            double theta = 2 * acos(dd / 2 / r);
            ans += pi * r * r - (theta * r * r - dd * sqrt(r * r - dd * dd / 4));
        }
        pre = x;
    }
    printf("%.10f",ans);

    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx