HDU 3622 Bomb Game(二分+2SAT)
2024-08-31 05:37:09
题意:有一个游戏,有n个回合,每回合可以在指定的2个区域之一放炸弹,炸弹范围是一个圈,要求每回合的炸弹范围没有重合。得分是炸弹半径最小的值。求可以得到的最大分数。
思路:二分+2SAT。
二分炸弹范围,再根据有无重合建图,用2SAT判定。
#include <cstdio> #include <cmath> #include <vector> #include <cstring> using namespace std; ; struct TwoSAT { int n; vector<]; ]; ],c; bool dfs(int x) { ]) return false; if(mark[x]) return true; mark[x]=true; S[c++]=x; ; i<G[x].size(); ++i) if(!dfs(G[x][i])) return false; return true; } void init(int n) { this->n=n; ; i<n*; ++i) G[i].clear(); memset(mark,,sizeof(mark)); } void add_clause(int x,int xval,int y,int yval) { x=x*+xval; y=y*+yval; G[x^].push_back(y); G[y^].push_back(x); } bool solve() { ; i<n*; i+=) { ]) { c=; if(!dfs(i)) { ) mark[S[--c]]=false; )) return false; } } } return true; } }; struct Point { int x,y; }; Point p[][]; 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); ; i<n; ++i); a<; ++a) ; j<n; ++j); b<; ++b) *d) solver.add_clause(i,a^,j,b^); return solver.solve(); } int main() { while(scanf("%d",&n)!=EOF) { ; i<n; ++i) { ; j<; ++j) scanf("%d%d",&p[i][j].x,&p[i][j].y); } ; solver.init(n); ; i<n; ++i); a<; ++a) ; j<n; ++j); b<; ++b) maxi=max(maxi,distan(p[i][a],p[j][b])); ,R=maxi; ; i<; ++i) { ; if(judge(mid)) L=mid; else R=mid; } printf("%.2lf\n",L); } ; }
最新文章
- 【Java EE 学习 36】【struts2】【struts2系统验证】【struts2 ognl值栈】【struts2 ongl标签】【struts2 UI标签】【struts2模型驱动和令牌机制】
- ffplay代码播放pcm数据
- Lua协程
- Unity5的AssetBundle的一点使用心得
- CSS权威指南-第三版--读书笔记
- 每天一个linux命令(47)--scp命令
- SHA1withRSA加签名和验签名
- day14.生成器迭代器作业
- java_xml_解析
- Pick the Right Shoes
- 【安全测试自学】初探web安全处测试(三)
- 洛谷P1781宇宙总统题解
- Flask恋爱的一瞬间
- 正确理解web交互中的cookie与session
- 长短时记忆网络(LSTM)
- cmd 字符串截取
- 重温PHP之冒泡排序
- Cockroachdb 一、系统环境
- 使用Python批量合并PDF文件(带书签功能)
- Ubuntu 安装Google浏览器