首页 > 其他 > 详细

BZOJ4561 JLOI2016圆的异或并(扫描线+平衡树)

时间:2018-12-07 19:23:54      阅读:180      评论:0      收藏:0      [点我收藏+]

  考虑一条扫描线从左到右扫过这些圆。观察某一时刻直线与这些圆的交点,可以发现构成一个类似括号序列的东西,括号的包含关系与圆的包含关系是相同的。并且当扫描线逐渐移动时,括号间的相对顺序不变。于是考虑用set维护这个括号序列,插入时统计被包含层数。这只需要查询后继括号,如果是右括号则被该括号包含,答案为该括号次数+1,否则处于同一层,答案与该括号相同。

  bzoj大概又出了一些奇怪的精度问题,用long double才过。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
#include<cassert>
using namespace std;
#define ll long long
#define N 200010
#define double long double
char getc(){char c=getchar();while ((c<A||c>Z)&&(c<a||c>z)&&(c<0||c>9)) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<0||c>9) {if (c==-) f=-1;c=getchar();}
    while (c>=0&&c<=9) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int n,cur,ans[N];
const double eps=1E-6;
ll tot;
double pos(int a,int b,int r,int op){return b+op*(sqrt(1ll*r*r-1ll*(cur-a)*(cur-a))+eps);}
struct data
{
    int x,y,r,i,op;
    bool operator <(const data&a) const
    {
        return pos(x,y,r,op)<pos(a.x,a.y,a.r,a.op);
    }
}a[N<<1];
multiset<data> q;
bool cmp(const data&a,const data&b)
{
    return a.x+a.op*a.r<b.x+b.op*b.r;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("bzoj4561.in","r",stdin);
    freopen("bzoj4561.out","w",stdout);
    const char LL[]="%I64d\n";
#else
    const char LL[]="%lld\n";
#endif
    n=read();
    for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].r=read(),a[i].op=-1,a[i].i=i;
    for (int i=n+1;i<=n+n;i++) a[i].x=a[i-n].x,a[i].y=a[i-n].y,a[i].r=a[i-n].r,a[i].op=1,a[i].i=a[i-n].i;
    sort(a+1,a+n+n+1,cmp);
    for (int i=1;i<=n+n;i++)
    {
        cur=a[i].x+a[i].op*a[i].r;
        if (a[i].op==1) q.erase((data){a[i].x,a[i].y,a[i].r,a[i].i,-1}),q.erase((data){a[i].x,a[i].y,a[i].r,a[i].i,1});
        else
        {
            q.insert((data){a[i].x,a[i].y,a[i].r,a[i].i,-1}),q.insert((data){a[i].x,a[i].y,a[i].r,a[i].i,1});
            set<data>::iterator it=q.find((data){a[i].x,a[i].y,a[i].r,a[i].i,1});
            it++;if (it!=q.end()) ans[a[i].i]=(*it).op==1?ans[(*it).i]^1:ans[(*it).i];
            if (ans[a[i].i]) tot-=1ll*a[i].r*a[i].r;else tot+=1ll*a[i].r*a[i].r;
        }
    }
    cout<<tot;
    return 0;
}

 

BZOJ4561 JLOI2016圆的异或并(扫描线+平衡树)

原文:https://www.cnblogs.com/Gloid/p/10082307.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!