hdu3622 Bomb Game--2-sat & 二分

原题链接：​​http://acm.hdu.edu.cn/showproblem.php?pid=3622​​

题意：一个二维坐标系，n行数据，每行两个坐标算作一组，从n组跳出n点，画圆，半径一样，要求不能相交，可以相切，求最大半径。

分析：我的思路是求出所有点的距离，排序，从大到小遍历2-sat，但是提交说内存爆了，实在没办法，用了网上的办法二分半径，真心无语。

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#define INF 99999999
#define eps 0.0001
using namespace std;

struct Node
{
  double x;
  double y;
};

int n;
int cnt;
int index;
Node node[200];
int dfn[205];
int low[205];
int belong[205];
bool inStack[205];
vector<int> vec[200];
double d[40005];
int ii;
stack<int> s;

double dis(Node node1, Node node2)
{
  return sqrt((node1.x - node2.x)*(node1.x - node2.x) + (node1.y - node2.y)*(node1.y - node2.y));
}

void tarjan(int u)
{
  low[u] = dfn[u] = ++index;
  inStack[u] = 1;
  s.push(u);
  for (int i = 0; i < vec[u].size(); i++)
  {
    int v = vec[u][i];
    if (!dfn[v])
    {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    }
    else if (inStack[v])
      low[u] = min(low[u], dfn[v]);
  }

  if (low[u] == dfn[u])
  {
    int p;
    cnt++;
    do
    {
      p = s.top();
      s.pop();
      inStack[p] = 0;
      belong[p] = cnt;
    } while (p != u);
  }
}

bool solve()
{
  cnt = index = 0;
  for (int i = 0; i < 2 * n; i++)
    if (!dfn[i])
      tarjan(i);

  for (int i = 0; i < 2 * n; i = i + 2)
    if (belong[i] == belong[i + 1])
      return false;

  return true;
}

int main()
{
  while (~scanf("%d", &n))
  {
    for (int i = 0; i < 2 * n; i = i + 2)//是+2，不是+1
      scanf("%lf%lf%lf%lf", &node[i].x, &node[i].y, &node[i ^ 1].x, &node[i ^ 1].y);

    double l = 0.0;
    double r = 40000.0;
    double ans = -1;
    while (r - l > eps)
    {
      double mid = (l + r) / 2;

      //init
      for (int i = 0; i < 2 * n; i++)
      {
        dfn[i] = 0;
        vec[i].clear();
        inStack[i] = 0;
      }

      for (int j = 0; j < 2 * n; j = j + 2)
        for (int k = j + 2; k < 2 * n; k++)
          if (dis(node[j], node[k]) < 2 * mid)
          {
            vec[j].push_back(k ^ 1);
            vec[k].push_back(j ^ 1);
          }
      for (int j = 1; j < 2 * n; j = j + 2)
        for (int k = j + 1; k < 2 * n; k++)
          if (dis(node[j], node[k]) < 2 * mid)
          {
            vec[j].push_back(k ^ 1);
            vec[k].push_back(j ^ 1);
          }

      if (solve())
      {
        l = mid;
        ans = mid;
      }
      else
        r = mid;
    }
    printf("%.2lf\n", ans);
  }

  return 0;
}