bzoj4561: [JLoi2016]圆的异或并圆的扫描线

2023-08-04 22:21:58

地址：http://www.lydsy.com/JudgeOnline/problem.php?id=4561

题目：

4561: [JLoi2016]圆的异或并

Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 700 Solved: 275
[Submit][Status][Discuss]

Description

在平面直角坐标系中给定N个圆。已知这些圆两两没有交点，即两圆的关系只存在相离和包含。求这些圆的异或面

积并。异或面积并为：当一片区域在奇数个圆内则计算其面积，当一片区域在偶数个圆内则不考虑。

Input

第一行包含一个正整数N，代表圆的个数。接下来N行，每行3个非负整数x,y,r，表示一个圆心在(x,y)，半径为r的

圆。保证|x|,|y|,≤10^8，r>0,N<=200000

Output

仅一行一个整数，表示所有圆的异或面积并除以圆周率Pi的结果。

Sample Input

2
0 0 1
0 0 2

Sample Output

HINT

思路：

　　和那个hdu3511一模一样有么有？

　　直接拿过来改改就ac了

/**************************************************************

    Problem: 4561

    User: weeping

    Language: C++

    Result: Accepted

    Time:3156 ms

    Memory:16888 kb

****************************************************************/

#include <bits/stdc++.h>

#define MP make_pair

using namespace std;

const double eps = 1e-;

const int N = 4e5+;

int n,cnt[N];

int cr[N][],r[N];

pair<int,int>pt[N];

double curx;

struct node

{

    int id,f;

    bool operator < (const node &ta) const

    {

        double y1 = cr[id][] + f * sqrt(1.0 *r[id]*r[id]-1.0*(curx-cr[id][])*(curx-cr[id][]));

        double y2 = cr[ta.id][] + ta.f * sqrt(1.0 *r[ta.id]*r[ta.id]-1.0*(curx-cr[ta.id][])*(curx-cr[ta.id][]));

        if(fabs(y1-y2)<eps)

            return f<ta.f;

        return y1<y2;

    }

};

set<node >st;

int main(void)

{

    int n;

    while(~scanf("%d",&n))

    {

        st.clear();

        int tot=;

        long long ans=;

        for(int i=;i<=n;i++)

        {

            scanf("%d%d%d",&cr[i][],&cr[i][],r+i);

            pt[tot++]=MP(cr[i][]-r[i],i);

            pt[tot++]=MP(cr[i][]+r[i],i-n);

            cnt[i]=;

        }

        sort(pt,pt+tot);

        for(int i=;i<tot;i++)

        {

            int k=pt[i].second,up=,dw=;

            curx = pt[i].first;

            if(k<=)

                k+=n,st.erase((node){k,-}),st.erase((node){k,});

            else

            {

                set<node>::iterator it=st.insert((node){k,-}).first;

                it++;

                if(it!=st.end())    up = it->id;

                it--;

                if(it!=st.begin())  dw = (--it)->id;

                if(up==dw&&up)

                    cnt[k]=cnt[up]+;

                else if(up&&dw)

                    cnt[k]=max(cnt[up],cnt[dw]);

                else

                    cnt[k]=;

                ans+=(cnt[k]&?:-)*1LL*r[k]*r[k];

                st.insert((node){k,});

            }

        }

        printf("%lld\n",ans);

    }

    return ;

}

码农公寓