HDU3622BombGame(2

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了HDU3622BombGame(2，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2352字，纯文字阅读大概需要4分钟。

内容图文

HDU 3622 Bomb Game(2-SAT二分) http://acm.hdu.edu.cn/showproblem.php?pid=3622 题意: 有N对地点,每对地点中的一个地方要放一个*,你可以控制*的爆炸半径,现在要求所有N个被放的*爆炸范围不重叠.问你在所有可行方案中的*爆炸最大半径是多少?(假

HDU 3622 Bomb Game(2-SAT+二分)

http://acm.hdu.edu.cn/showproblem.php?pid=3622

题意:

有N对地点,每对地点中的一个地方要放一个*,你可以控制*的爆炸半径,现在要求所有N个被放的*爆炸范围不重叠.问你在所有可行方案中的*爆炸最大半径是多少?(假设所有*爆炸半径相同,本假设与原提议的要求等价,可以自己想想)

分析:

直接二分可能的爆炸半径mid,然后对于mid来说,遍历任意两点的所有组合.如果a=0的点与b=1的点的距离<mid ,那么a=0,b=1点就不能同时存在.则 add_clause(a,0,b,0) 且add_clause(b,1,a,1).

AC代码:

#include
#include
#include
#include
using namespace std;
const int maxn=100+10;
int n;
struct TwoSAT
{
    int n;
    vector G[maxn*2];
    int S[maxn*2],c;
    bool mark[maxn*2];

    bool dfs(int x)
    {
        if(mark[x^1]) return false;
        if(mark[x]) return true;
        mark[x]=true;
        S[c++]=x;

        for(int i=0;i<G[x].size();i++)
            if(!dfs(G[x][i])) return false;
        return true;
    }

    void init(int n)
    {
        this->n=n;
        for(int i=0;i<2*n;i++) G[i].clear();
        memset(mark,0,sizeof(mark));
    }

    void add_clause(int x,int xval,int y,int yval)
    {
        x = x*2+xval;
        y = y*2+yval;
        G[x].push_back(y);
    }

    bool solve()
    {
        for(int i=0;i<2*n;i+=2)
        if(!mark[i] && !mark[i+1])
        {
            c=0;
            if(!dfs(i))
            {
                while(c>0) mark[S[--c]]=false;
                if(!dfs(i+1)) return false;
            }
        }
        return true;
    }
}TS;
struct Point
{
    double x,y;
};
struct Node
{
    Point p[2];
}s[maxn];
double dist(int i,int vi,int j,int vj)
{
    double x1,y1,x2,y2;
    x1 = s[i].p[vi].x;
    y1 = s[i].p[vi].y;
    x2 = s[j].p[vj].x;
    y2 = s[j].p[vj].y;
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
bool ok(double mid)
{
    TS.init(n);
    for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
    {
        if(dist(i,0,j,0) < mid*2) //冲突
        {
            TS.add_clause(i,0,j,1);
            TS.add_clause(j,0,i,1);
        }
        if(dist(i,1,j,0) < mid*2) //冲突
        {
            TS.add_clause(i,1,j,1);
            TS.add_clause(j,0,i,0);
        }
        if(dist(i,0,j,1) < mid*2) //冲突
        {
            TS.add_clause(i,0,j,0);
            TS.add_clause(j,1,i,1);
        }
        if(dist(i,1,j,1) < mid*2) //冲突
        {
            TS.add_clause(i,1,j,0);
            TS.add_clause(j,1,i,0);
        }
    }
    return TS.solve();
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&s[i].p[0].x,&s[i].p[0].y,&s[i].p[1].x,&s[i].p[1].y);
        }
        double L=0.0, R=20000.1;
        while(R-L > (1e-4) )
        {
            double mid = (R+L)/2;
            if(ok(mid)) L=mid;
            else R=mid;
        }
        printf("%.2lf\n",L);
    }
    return 0;
}

内容总结

以上是互联网集市为您收集整理的HDU3622BombGame(2全部内容，希望文章能够帮你解决HDU3622BombGame(2所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端