首页 > 代码库 > HDU 3622 Bomb Game(二分+2SAT)

HDU 3622 Bomb Game(二分+2SAT)

2024-07-17 19:15:34   213人阅读

题意：有一个游戏，有n个回合，每回合可以在指定的2个区域之一放炸弹，炸弹范围是一个圈，要求每回合的炸弹范围没有重合。得分是炸弹半径最小的值。求可以得到的最大分数。

思路：二分+2SAT。

二分炸弹范围，再根据有无重合建图，用2SAT判定。

#include <cstdio>#include <cmath>#include <vector>#include <cstring>using namespace std;const int maxn =105;struct TwoSAT{    int n;    vector<int> G[maxn*2];    bool mark[maxn*2];    int S[maxn*2],c;    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<n*2; ++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^1].push_back(y);        G[y^1].push_back(x);    }    bool solve()    {        for(int i=0; i<n*2; 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;    }};struct Point{    int x,y;};Point p[105][2];int n;TwoSAT solver;double distan(Point a,Point b){    return sqrt((a.x*1.0-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}bool judge(double d){    solver.init(n);    for(int i=0; i<n; ++i)for(int a=0; a<2; ++a)            for(int j=i+1; j<n; ++j)for(int b=0; b<2; ++b)                    if(distan(p[i][a],p[j][b])<=2*d)                        solver.add_clause(i,a^1,j,b^1);    return solver.solve();}int main(){    while(scanf("%d",&n)!=EOF)    {        for(int i=0; i<n; ++i)        {            for(int j=0; j<2; ++j)                scanf("%d%d",&p[i][j].x,&p[i][j].y);        }        double maxi=0;        solver.init(n);        for(int i=0; i<n; ++i)for(int a=0; a<2; ++a)                for(int j=i+1; j<n; ++j)for(int b=0; b<2; ++b)                        maxi=max(maxi,distan(p[i][a],p[j][b]));        double L=0,R=maxi;        for(int i=0; i<30; ++i)        {            double mid=(L+R)/2;            if(judge(mid)) L=mid;            else R=mid;        }        printf("%.2lf\n",L);    }    return 0;}
View Code

 


联系
我们