BZOJ 1822 計算幾何+網絡流+二分答案 解題報告

1822: [JSOI2010]Frozen Nova 冷凍波

Description

WJJ喜歡“魔獸争霸”這個遊戲。在遊戲中，巫妖是一種強大的英雄，它的技能Frozen Nova每次可以殺死一個小精靈。我們認為，巫妖和小精靈都可以看成是平面上的點。 當巫妖和小精靈之間的直線距離不超過R，且巫妖看到小精靈的視線沒有被樹木阻擋（也就是說，巫妖和小精靈的連線與任何樹木都沒有公共點）的話，巫妖就可以瞬間殺滅一個小精靈。 在森林裡有N個巫妖，每個巫妖釋放Frozen Nova之後，都需要等待一段時間，才能再次施放。不同的巫妖有不同的等待時間和施法範圍，但相同的是，每次施放都可以殺死一個小精靈。 現在巫妖的頭目想知道，若從0時刻開始計算，至少需要花費多少時間，可以殺死所有的小精靈？

Input

輸入檔案第一行包含三個整數N、M、K(N,M,K<=200)，分别代表巫妖的數量、小精靈的數量和樹木的數量。 接下來N行，每行包含四個整數x, y, r, t，分别代表了每個巫妖的坐标、攻擊範圍和施法間隔（機關為秒）。 再接下來M行，每行兩個整數x, y，分别代表了每個小精靈的坐标。 再接下來K行，每行三個整數x, y, r，分别代表了每個樹木的坐标。 輸入資料中所有坐标範圍絕對值不超過10000，半徑和施法間隔不超過20000。

Output

輸出一行，為消滅所有小精靈的最短時間（以秒計算）。如果永遠無法消滅所有的小精靈，則輸出-1。

Sample Input

2 3 1

-100 0 100 3

100 0 100 5

-100 -10

100 10

110 11

5 5 10

Sample Output

5

Source

JSOI2010第二輪Contest1

【解題報告】

經典建圖方式，二分答案，S到巫妖王的容量（總時間/冷卻時間）改變。

對于判斷樹木是否與線段相交，分兩種情況讨論：

1:圓心作線段的垂線垂足不線上段上

方法：直接比較圓心與線段兩個端點距離的最小值是否小于半徑

2:圓心作線段的垂線垂足線上段上

方法：算出垂線長度後比較

區分1、2兩種情況用點積即可，相當于間接判斷cos的值得正負

代碼如下：

/**************************************************************
    Problem: 1822
    User: onepointo
    Language: C++
    Result: Accepted
    Time:220 ms
    Memory:2192 kb
****************************************************************/

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define N 10000
#define inf 0x3f3f3f3f

int n,m,k;
int head[N],vis[N],cnt=;
int S,T,cur[N],mp[][],mark[];
struct Point {double x,y;};
struct Lich {double x,y,r;int t;}li[];
struct Spirit {double x,y;}sp[];
struct Tree {double x,y,r;}tr[];
struct Edge {int to,nxt,w;}e[N<<];

void adde(int u,int v,int w)
{
    e[++cnt].w=w;e[cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
    e[++cnt].w=;e[cnt].to=u;e[cnt].nxt=head[v];head[v]=cnt;
}
double qdis(Lich a,Spirit b)
{
    return sqrt(pow((a.x-b.x),)+pow((a.y-b.y),));
}
double dis(double a,double b,double c,double d)
{
    return sqrt(pow((a-c),)+pow((b-d),));
}
double Cross(Point a,Point b,Point c)
{
    double x1=b.x-a.x,y1=b.y-a.y;
    double x2=c.x-a.x,y2=c.y-a.y;
    return x1*y2-x2*y1;
}
double dot(Point a,Point b,Point c)
{
    double x1=b.x-a.x,y1=b.y-a.y;
    double x2=c.x-a.x,y2=c.y-a.y;
    return x1*x2+y1*y2;
}
bool in_cir(Lich a,Spirit b,Tree c)
{
    Point tmp1,tmp2,tmp3;
    tmp1=(Point){a.x,a.y};
    tmp2=(Point){b.x,b.y};
    tmp3=(Point){c.x,c.y};
    if(dot(tmp3,tmp1,tmp2)>=) return min(dis(a.x,a.y,c.x,c.y),dis(b.x,b.y,c.x,c.y))<=c.r;
    else return abs(Cross(tmp1,tmp3,tmp2))/qdis(a,b)<=c.r;
}

bool bfs()
{
    memset(vis,-,sizeof(vis));
    queue<int>q;q.push(S);vis[S]=;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(vis[v]==-&&e[i].w)
                vis[v]=vis[u]+,q.push(v);
        }
    }
    return vis[T]!=-;
}
int dfs(int x,int f)
{
    if(!f||x==T) return f;
    int w,used=;
    for(int i=cur[x];i;i=e[i].nxt)
        if(vis[e[i].to]==vis[x]+)
        {
            w=f-used;
            w=dfs(e[i].to,min(w,e[i].w));
            e[i].w-=w;e[i^].w+=w;
            used+=w; 
            if(e[i].w) cur[x]=i;
            if(used==f) return used;
        }
    if(!used) vis[x]=-;
    return used;
}
int Dinic()
{
    int ret=;
    while(bfs())
    {
        for(int i=S;i<=T;++i) cur[i]=head[i];
        ret+=dfs(S,inf);
    }
    return ret;
}
bool check(int x)
{
    cnt=;
    memset(head,,sizeof(head));
    for (int i=;i<=n;++i)
    {
        int tmp=x/li[i].t+;
        adde(S,i,tmp);
    }
    for(int i=;i<=n;++i)
    for(int j=;j<=m;++j)
        if(mp[i][j]) adde(i,j+n,);
    for(int i=;i<=m;++i) adde(i+n,T,);
    return Dinic()==m;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    S=;T=n+m+;
    for(int i=;i<=n;++i) scanf("%lf%lf%lf%d",&li[i].x,&li[i].y,&li[i].r,&li[i].t);
    for(int i=;i<=m;++i) scanf("%lf%lf",&sp[i].x,&sp[i].y);
    for(int i=;i<=k;++i) scanf("%lf%lf%lf",&tr[i].x,&tr[i].y,&tr[i].r);
    for(int i=;i<=n;++i)
    for(int j=;j<=m;++j)
    {
        double dist=qdis(li[i],sp[j]);
        if(dist>li[i].r) continue;
        bool flag=;
        for(int _k=;_k<=k;++_k)
            if(in_cir(li[i],sp[j],tr[_k])) {flag=;break;}
        if(flag) mp[i][j]=,mark[j]=;
    }
    for(int i=;i<=m;++i)
        if(!mark[i]) {printf("-1\n");return ;}
    int l=,r=inf,ans=inf;
    while(l<=r)
    {
        int mid=(l+r)>>;
        if(check(mid)) r=mid-,ans=min(ans,mid);
        else l=mid+;
    }
    printf("%d\n",ans==inf?-:ans);
    return ;
}