本文共 1180 字，大约阅读时间需要 3 分钟。
【题目链接】
【题目大意】
要在坐标轴上放N次炸弹，每次可以选择两个位置中的一个位置放置，每个炸弹都可以控制它的爆炸范围（以放置位置为圆心的半径为r的圆圈），问半径最大可以多少，使得任意两个炸弹的爆炸范围都不重合。
【思路】
类似与 ， 但是判断重合的方法容易多了，果断1Y
注意精度问题。
【代码】
#include #include #include #include #include #include #define SQ(x) ((x)*(x))using namespace std;const int MAXN = 110;const int VN = MAXN*2;const int EN = VN*VN*2;const int INF = 0x3f3f3f3f;const double eps = 1e-9;int n;vector g[VN];struct Node{ int x, y; void input(){scanf("%d%d",&x,&y);}}arr[MAXN][2];void init(){ for(int i=0; i<2*n; ++i) g[i].clear();}void addEdge(int u, int v){ g[u].push_back(v);}class Two_Sat{public: bool check(){ scc(); for(int i=0; i eps) { //上， 上 addEdge(i, j+n); addEdge(j, i+n); } if(2*r - getDist(arr[i][0], arr[j][1]) > eps) { //上， 下 addEdge(i, j); addEdge(j+n, i+n); } if(2*r - getDist(arr[i][1], arr[j][0]) > eps){ // 下，上 addEdge(i+n, j+n); addEdge(j, i); } if(2*r - getDist(arr[i][1], arr[j][1]) > eps){ // 下，下 addEdge(i+n, j); addEdge(j+n, i); } } }}int main(){ while(~scanf("%d", &n)){ for(int i=0; i eps){ m = (r+l)/2.0; // 建图 buildGraph(m); if(sat.check()){ l = m+eps; ans = m; } else r=m; } printf("%.2f\n", ans); } return 0;}
转载地址：http://ppzni.baihongyu.com/