CF1055G
2022-04-25 23:00:15

首先考慮解決一個子問題：如何判斷答案是否是 (0)。假設(shè) Bob 的多邊形是 (P)，水母沒有活動區(qū)域，那么顯然只有當(dāng)水母在 (P) 中時 Bob 才會被蜇。換而言之，假設(shè)會使 Bob 被蜇的區(qū)域為禁止區(qū)域，那么這個禁止區(qū)域就是每只水母周圍的多邊形?？紤]再加上水母半徑為 (r) 的活動范圍，類似于【JSOI2018】戰(zhàn)爭，禁止區(qū)域為多邊形 (-P) 與半徑為 (r) 的圓的閔可夫斯基和。

由于會出現(xiàn)兩只水母的活動范圍有重疊的情況，此時 Bob 便不能從這兩只水母之間通過。具體的，假設(shè)這兩只水母的活動區(qū)域分別為 (r_1) 和 (r_2)，中心分別為 ((x_1,y_1)) 和 ((x_2,y_2))，如果 ((x_1-x_2,y_1-y_2)) 在 (P) 與半徑為 (r_1+r_2) 的圓的閔可夫斯基和中，Bob 便不能經(jīng)過這兩只水母之間。實現(xiàn)上可以通過找該向量到 (P) 與 (-P) 的閔可夫斯基和的距離與 (r_1+r_2) 進(jìn)行比較即可。需要注意的是題目所給定條件可以讓兩者相對精度差到 (10^{-17}) 左右，因此不能直接用浮點數(shù)計算。

并且注意到可以在泳池邊界和水母之間經(jīng)過?？紤]構(gòu)造一個圖，令邊界和每只水母都是頂點，如果兩只水母之間不能經(jīng)過這兩個頂點就連一條邊（可以發(fā)現(xiàn)這就是對偶圖）。如果平面圖上下連通（答案為 (0)），這就相當(dāng)于對偶圖左邊界對應(yīng)點于右邊界對應(yīng)點不連通。否則如果連通，則 Bob 一定會被蟄。

然后考慮原來問題，我們所要求的就是刪去盡量少的水母，使 Bob 不被蟄。這是一個標(biāo)準(zhǔn)的網(wǎng)絡(luò)流形式：求最小割點數(shù)量。將原圖中水母所對應(yīng)的頂點拆成兩個點，連一條容量為 (1) 的邊，然后直接跑最小割就行了。

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define R(i,a,b) for(int i=(a),i##E=(b);i<=i##E;i++)
#define L(i,a,b) for(int i=(b),i##E=(a);i>=i##E;i--)
using namespace std;
const ll inf=1ll<<30;
int n,w,m;
struct point
{
    int x,y;
    inline point (int X=0,int Y=0):x(X),y(Y) {}
    inline point operator +(const point &A)const
    {
        return point(x+A.x,y+A.y);
    }
    inline point operator -(const point &A)const
    {
        return point(x-A.x,y-A.y);
    }
    inline ll dot(const point &A)
    {
        return 1ll*x*A.x+1ll*y*A.y;
    }
    inline ll det(const point &A)
    {
        return 1ll*x*A.y-1ll*y*A.x;
    }
    inline int operator <(const point &A)const
    {
        return x==A.x?y<A.y:x<A.x;
    }
    inline ll abs2() 
    {
        return 1ll*x*x+y*y;
    }
};
vector<point>a,b;
int top;

int tim,S,T,id[222][2];

struct ccl
{
    point o;
    int r;
};
vector<ccl>c;
int lb,rb;

inline vector<point> init(vector<point> a)
{
    vector<point>t;
    int p=min_element(a.begin(),a.end())-a.begin();
    R(i,0,a.size()-1) t.emplace_back(a[(i+p)%a.size()]);
    return t;
}
inline vector<point> mincowski(vector<point>a,vector<point>b)
{
    a=init(a),b=init(b);
    vector<point>t,A(a.size()),B(b.size());
    R(i,0,a.size()-1) A[i]=a[(i+1)%a.size()]-a[i];
    R(i,0,b.size()-1) B[i]=b[(i+1)%b.size()]-b[i];

    int i=0,j=0;
    t.emplace_back(a[0]+b[0]);
    while(i<a.size()||j<b.size())
    {
        if(i==a.size()) t.emplace_back(t.back()+B[j]),++j;
        else if(j==b.size()) t.emplace_back(t.back()+A[i]),++i;
        else if(A[i].det(B[j])>=0) t.emplace_back(t.back()+A[i]),++i;
        else t.emplace_back(t.back()+B[j]),++j;
    }
    t.pop_back();
    return t;    
}
inline int check_onseg(point p,point x,point y)
{
    return ((p-x).det(p-y))==0&&((p-x).dot(p-y))<=0;
}
inline int check(point a,ll r,vector<point>q)
{
    for(auto b:q) if((a-b).abs2()<r*r) return 1;
    int ok=1;    
    R(i,0,q.size()-1)
    {
        point x=q[i],y=q[(i+1)%q.size()];
        if(check_onseg(a,x,y)) return 1;
        if((a-x).dot(y-x)>0&&(a-y).dot(x-y)>0)
        {
            ll t=(a-x).det(y-x);
            if(t*t<r*r*(y-x).abs2()) return 1;
        }
        ok&=((a-x).det(y-x)<=0);
    }
    return ok;
}
struct edge
{
    int to,nxt,f;
}e[166666];
int head[444],dis[444],cnt=1;
int q[444];
inline void add_edge(int u,int v,int d)
{
    e[++cnt]=(edge){v,head[u],d};
    head[u]=cnt;
    e[++cnt]=(edge){u,head[v],0};
    head[v]=cnt;
}
int bfs()
{
    memset(dis,-1,sizeof(dis));
    int h=0,t=1;
    q[1]=S;dis[S]=0;
    while(h!=t)
    {
        int u=q[++h];
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(dis[v]==-1&&e[i].f)
            {
                dis[v]=dis[u]+1;
                if(v==T) return 1;
                q[++t]=v;
            }
        }
    }
    return 0;
}
int dfs(int u,int flow)
{
    if(u==T) return flow;
    int del=flow;
    for(int i=head[u];i&&del;i=e[i].nxt)
    {
        int v=e[i].to;
        if(dis[v]==dis[u]+1&&e[i].f)
        {
            int k=dfs(v,min(e[i].f,del));
            e[i].f-=k;
            e[i^1].f+=k;
            del-=k;
        }
    }
    if(del) dis[u]=-1;
    return flow-del;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>w;
    lb=166666,rb=-166666;
    a.resize(n),b.resize(n);
    R(i,0,n-1)
    {
        int x,y;
        cin>>x>>y;
        a[i]=point(x,y),b[i]=point(-x,-y);
        lb=min(lb,x),rb=max(rb,x);
    }
    cin>>m;    
    R(i,1,m) id[i][0]=++tim,id[i][1]=++tim;
    S=++tim;
    T=++tim;
    c.resize(m+1);
    R(i,1,m) cin>>c[i].o.x>>c[i].o.y>>c[i].r;
    a=mincowski(a,b);
    R(i,1,m)
    {
        add_edge(id[i][0],id[i][1],1);
        if(rb-lb>c[i].o.x-c[i].r) add_edge(S,id[i][0],inf);
        if(rb-lb>w-c[i].o.x-c[i].r) add_edge(id[i][1],T,inf);
    }
    R(i,1,m) R(j,i+1,m) if(check(c[i].o-c[j].o,c[i].r+c[j].r,a))
    {
        add_edge(id[j][1],id[i][0],inf);
        add_edge(id[i][1],id[j][0],inf);
    }
    int ans=0;
    while(bfs()) ans+=dfs(S,inf);
    cout<<ans<<'
';
}