Bomb Game（二分 2-SAT）

传送门

题意

略

分析

要求最大的合法半径。
可以考虑二分，每次check重新建图跑tarjan判断是否合法。
小于ans的半径一定合法，本题是有二分性质的。
（数组开小了一直T调了好久）

代码

#include <bits/stdc++.h>using namespace std;
//-----pre_def----
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define fir(i, a, b) for (int i = (a); i <= (b); i++)
#define rif(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
#define init_h memset(h, -1, sizeof h), idx = 0;
#define lowbit(x) x &(-x)//---------------
const int N = 200 + 10;
const double eps = 1e-5;
double a[N], b[N], c[N], d[N];
int read()
{
    int ret = 0, flag = 0;char ch;if ((ch = getchar()) == '-')flag = 1;else if (ch >= '0' && ch <= '9')ret = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9')ret = ret * 10 + (ch - '0');return flag ? -ret : ret;
}
struct two_SAT
{
    int n; //未翻倍之前的点数bool in_stack[N];int id[N], stk[N], top, dfn[N], low[N], times, scc_cnt; //所在scc编号，栈，dfs序，最下能到哪个节点，时间戳，scc编号int h[N], e[N*N], ne[N*N], idx;//这里数组开小了，一直TLE，，，void init(int _n){
    n = _n;init_h;}void over(){
    memset(id, 0, sizeof id);memset(dfn, 0, sizeof dfn);memset(low, 0, sizeof low);memset(in_stack,0,sizeof in_stack);times = top = scc_cnt = 0;}inline void add(int a, int b){
    e[idx] = b;ne[idx] = h[a];h[a] = idx++;}inline void add_and(int x, int valx, int y, int valy) //如果x取valx，则y必须取valy{
    //x -> y or !x -> y or x -> !y or !x -> !yadd(x + valx * n, y + valy * n);}void add_or(int x, int valx, int y, int valy) //x取valx 或 y取valy{
    add(x + (!valx) * n, y + valy * n);add(y + (!valy) * n, x + valx * n);}void add_one(int x, int valx){
    add_or(x, valx, x, valx);}bool check(double x1, double y1, double x2, double y2, double r){
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) < 2 * 2 * r * r;}void build(double dis){
    fir(i, 1, n){
    fir(j, i + 1, n){
    //i,j;if (check(a[i], b[i], a[j], b[j], dis)){
    add_and(i, 0, j, 1);add_and(j, 0, i, 1);}if (check(a[i], b[i], c[j], d[j], dis)){
    add_and(i, 0, j, 0);add_and(j, 1, i, 1);}if (check(c[i], d[i], a[j], b[j], dis)){
    add_and(i, 1, j, 1);add_and(j, 0, i, 0);}if (check(c[i], d[i], c[j], d[j], dis)){
    add_and(i, 1, j, 0);add_and(j, 1, i, 0);}}}}void tarjan(int u){
    dfn[u] = low[u] = ++times;stk[++top] = u, in_stack[u] = true;for (int i = h[u]; ~i; i = ne[i]){
    int j = e[i];if (!dfn[j]){
    tarjan(j);low[u] = min(low[u], low[j]);}else if (in_stack[j]){
    low[u] = min(low[u], dfn[j]);}}if (dfn[u] == low[u]){
    ++scc_cnt;int y;do{
    y = stk[top--];in_stack[y] = false;id[y] = scc_cnt;} while (y != u);}}void tarjan(){
    fir(i, 1, n << 1) if (!dfn[i])tarjan(i);}bool solve(){
    tarjan();for (int i = 1; i <= n; i++)if (id[i] == id[i + n])return false;return true;}
} t;void init() {
    }
int main()
{
    
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);int StartTime = clock();
#endifint n;while (~scanf("%d", &n)){
    fir(i, 1, n){
    scanf("%lf%lf%lf%lf", &a[i], &b[i], &c[i], &d[i]);}double l = 0, r = 40000;while(r-l>eps){
    double mid = (l + r) / 2.0;t.init(n);t.build(mid);if (t.solve()){
    l = mid;}else{
    r = mid;}t.over();}printf("%.2lf\n", l);}
#ifndef ONLINE_JUDGEprintf("Run_Time = %d ms\n", clock() - StartTime);
#endifreturn 0;
}