fzyzojP2119 -- 圆圈游戏

冷不防 2022-01-12 10:43 192阅读 0赞

![1399631-20190210152215459-1240449877.png][]

![1399631-20190210152249243-1267254383.png][]

说白了，就是这个样子：

![1399631-20190210152347911-512465854.png][]

这个玩意明显是一个优美的树形结构

是个森林

然后建个虚点0，并且w\[0\]=0，然后树形dp即可

f\[x\]=max(w\[x\],∑f\[son\])

难点是：树怎么建？

就要上计算几何了：

如果我们用扫描线扫过去

发现，同时存在的两个圆，由于不相交，不相切，所以 相对位置始终保持不变

或者说，不论扫到哪个位置，两个圆的四个纵坐标的相对大小是固定的。

![1399631-20190210152806334-1064916043.png][]

基于这个优秀的事实，

判断圆的相互包含关系，这样处理：

![1399631-20190210153038947-1847144894.png][]

![1399631-20190210153158882-1817429474.png][]

画个图就明白了

这个都是基于：“纵坐标相对大小不变”的事实，所以，不管扫描线怎么动，虽然纵坐标变了，但是不用重新建平衡树，因为形态还是不变的

这使得插入的时候，这个树还是正确的，直接找前驱就是对的了

用set就可以

重载小于号，用全局变量P来比较（只有插入和查询前驱的时候会进行比较）

（比较的第二关键字还是有用的，因为同时插入两个半圆壳，纵坐标那个时候是相同的）

由于会出现r=0的情况，所以扫描线的处理，横坐标相同，插入在前，删除在后。

代码：

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define numb (ch^'0')
    using namespace std;
    typedef long long ll;
    il void rd(ll &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    namespace Miracle{
    const int N=100000+5;
    int n;
    ll P;//PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
    struct circle{
        ll x,y,r;
        int w;
        long double calc(ll p,int fl){
            return (long double)y+fl*sqrt((long double)r*r-(long double)(p-x)*(p-x));            
        }
    }c[N];
    struct po{
        int id,fl;//fl=1 up; fl=-1 down
        po(){}
        po(int x,int y){
            id=x;fl=y;
        }
        bool friend operator <(po a,po b){
            if(c[a.id].calc(P,a.fl)!=c[b.id].calc(P,b.fl)) return c[a.id].calc(P,a.fl)<c[b.id].calc(P,b.fl);
            return a.fl<b.fl;
        }
    };
    set<po>s;
    set<po>::iterator it;
    struct que{
        int pos,id,typ;
        bool friend operator <(que a,que b){
            if(a.pos!=b.pos)return a.pos<b.pos;
            return a.typ>=b.typ;
        }
    }q[2*N];
    int tot;
    struct node{
        int nxt,to;
    }e[2*N];
    int hd[N],cnt;
    int du[N];
    int fa[N];
    void add(int x,int y){
        e[++cnt].nxt=hd[x];
        e[cnt].to=y;
        hd[x]=cnt;
    }
    int f[N];
    bool vis[N];
    void dfs(int x){
        vis[x]=1;
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(!vis[y]){
                dfs(y);
                f[x]+=f[y];
            }
        }
        f[x]=max(f[x],c[x].w);
    }
    int main(){
        scanf("%d",&n);
        for(reg i=1;i<=n;++i){
            rd(c[i].x);rd(c[i].y);rd(c[i].r);//rd(c[i].w);
            scanf("%d",&c[i].w);
            q[++tot].pos=c[i].x-c[i].r;
            q[tot].id=i;q[tot].typ=1;
            
            q[++tot].pos=c[i].x+c[i].r;
            q[tot].id=i;q[tot].typ=-1;
        }
        sort(q+1,q+tot+1);
        for(reg i=1;i<=tot;++i){
            P=q[i].pos;
        //    cout<<q[i].pos<<" "<<q[i].id<<" "<<q[i].typ<<endl;
        //    cout<<c[1].calc(P,1)<<" and "<<c[1].calc(P,-1)<<" "<<c[q[i].id].calc(P,1)<<endl;
            if(q[i].typ==1){
                it=s.upper_bound(po(q[i].id,1));
                if(it!=s.end()){
                    if((*it).fl==1){
                    //    cout<<" find up "<<endl;
                        fa[q[i].id]=(*it).id;
                        add((*it).id,q[i].id);
                    }else{
                        fa[q[i].id]=fa[(*it).id];
                        add(fa[(*it).id],q[i].id);
                    }
                }else{
                    fa[q[i].id]=0;
                    add(0,q[i].id);
                }
                s.insert(po(q[i].id,1));
                s.insert(po(q[i].id,-1));
            }else{
                s.erase(po(q[i].id,1));
                s.erase(po(q[i].id,-1));
            }
        }
        dfs(0);
        printf("%d\n",f[0]);
        return 0;
    }
    
    }
    signed main(){
        freopen("2.in","r",stdin);
        freopen("2.out","w",stdout);
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
       Date: 2019/2/10 8:46:45
    */

转载于:https://www.cnblogs.com/Miracevin/p/10359299.html

[1399631-20190210152215459-1240449877.png]: /images/20220109/6ec4966f7dd540c795a2b778eaea0cb8.png
[1399631-20190210152249243-1267254383.png]: /images/20220109/18fc254e8be14edd9deca66cee7c8f9a.png
[1399631-20190210152347911-512465854.png]: /images/20220109/377eaa19396143aea0b35d1b0c2a4f19.png
[1399631-20190210152806334-1064916043.png]: /images/20220109/c864a179a50e42d5bb9be85f6d312456.png
[1399631-20190210153038947-1847144894.png]: /images/20220109/648893b973f74991b678540d7d151d4d.png
[1399631-20190210153158882-1817429474.png]: /images/20220109/458e35a1f6e6424faa416efbd9e3471c.png