题意：给你N组气球，每组有2个气球，每组要取一个气球，问最后使得N个气球都不相交，则气球半径R最大是多少。
思路：直接二分半径，然后2-sat判可行性。SCC之后如果有两个同组的点在同一个强联通分量里，那么则不可行。
这道题注意最后的二分结束之后还要取三位小数，看取了之后是否还是符合情况的，最后的那个 操作是看别人的。。我WA到死了。。
我感觉这题这里太坑了。。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;
int t ;
#define N 2005
double x[N << 1] , y[N << 1] ,z[N << 1] ;
struct kdq{
int e , next ;
}ed[N * 100] ;
int head[N] , num ;
int dfn[N << 1] , low[N << 1] ,st[N << 1] , top , dp ,inst[N << 1] , ca ,belong[N << 1] ;
void add(int s ,int e){
ed[num].e = e ;
ed[num].next = head[s] ;
head[s] = num ++ ;
}
void init(){
mem(head , -1) ;
num = 0 ;
mem(dfn ,0) ;
mem(low, 0) ;
mem(st ,0) ;
mem(inst ,0) ;
mem(belong ,0) ;
top = dp = ca = 0 ;
}
inline double getdis(int i ,int j){
return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) + (z[i] - z[j]) * (z[i] - z[j])) ;
}
void tarjan(int now){
low[now] = dfn[now] = ++ dp ;
st[top ++] = now ;
inst[now] = 1 ;
for (int i = head[now] ; ~i ; i = ed[i].next ){
int e = ed[i].e ;
if(!dfn[e]){
tarjan(e) ;
low[now] = min(low[now] , low[e]) ;
}
else if(inst[e]){
low[now] = min(low[now] , dfn[e]) ;
}
}
if(low[now] == dfn[now]){
ca ++ ;
int xx ;
do{
xx = st[-- top] ;
belong[xx] = ca ;
inst[xx] = 0 ;
}while(xx != now) ;
}
}
void build(double mid){
init() ;
for (int i = 0 ; i < t ; i ++ ){
for (int j = i + 1 ; j < t ; j ++ ){
if(getdis(LL(i),LL(j)) < mid){
add(LL(i) , LL(j) ^ 1) ;
add(LL(j) , LL(i) ^ 1) ;
}
if(getdis(LL(i) ,RR(j)) < mid){
add(LL(i) , RR(j) ^ 1) ;
add(RR(j) , LL(i) ^ 1) ;
}
if(getdis(RR(i) , LL(j)) < mid){
add(RR(i) , LL(j) ^ 1) ;
add(LL(j) , RR(i) ^ 1) ;
}
if(getdis(RR(i) , RR(j)) < mid){
add(RR(i) , RR(j) ^ 1) ;
add(RR(j) , RR(i) ^ 1) ;
}
}
}
}
int fuckit(){
for (int i = 0 ; i < t << 1 ; i ++ ){
top = dp = 0 ;
if(!dfn[i])tarjan(i) ;
}
for (int i = 0 ; i < t ; i ++ ){
if(belong[LL(i)] == belong[RR(i)])return 0 ;
}
return 1 ;
}
int main() {
while(cin >> t){
for (int i = 0 ; i < t ;i ++ ){
cin >> x[LL(i)] >> y[LL(i)] >> z[LL(i)] ;
cin >> x[RR(i)] >> y[RR(i)] >> z[RR(i)] ;
}
// cout << getdis(0 ,1) << endl;
double l = 0 , r = 20000 ;
double mid ;
while(r - l > 1e-5){
mid = (l + r) / 2 ;
build(mid) ;
if(fuckit()){
l = mid ;
}
else r = mid ;
}
double ans = mid / 2 ;//直接输出 mid / 2 就WA到死。
char aa[222] ;//太恶心。
sprintf(aa ,"%.3f" , ans) ;
sscanf(aa , "%lf" ,&ans) ;
build(ans * 2 ) ;
if(!fuckit())ans -= 0.001 ;
printf("%.3f\n",ans) ;
}
return 0 ;
}
HDU 3622
两道题其实完全是一样的，不过一题是3D，一题是2D，解法完全相同，不过这题二分之后不需要判可行性了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;
#define N 105
double x[N << 1] , y[N << 1] ;
struct kdq{
int e , next ;
}ed[N * 1000] ;
int dfn[N << 1] ,low[N << 1] , belong[N << 1] ,st[N << 1] ,inst[N << 1] ,head[N << 1] ;
int dp , top , ca , num , n ;
inline double getdis(int i ,int j){
return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) ;
}
void add(int s ,int e){
ed[num].e = e ;
ed[num].next = head[s] ;
head[s] = num ++ ;
}
void init(){
mem(dfn ,0) ;
mem(low ,0) ;
mem(st ,0) ;
mem(head,-1) ;
mem(belong ,0) ;
mem(inst ,0) ;
dp = top = ca = num = 0 ;
}
void build(double mid){
init() ;
for (int i = 0 ; i < n ; i ++ ){
for (int j = i + 1 ; j < n ; j ++ ){
if(getdis(LL(i) , LL(j)) < mid){
add(LL(i) , LL(j) ^ 1) ;
add(LL(j) , LL(i) ^ 1) ;
}
if(getdis(LL(i) , RR(j)) < mid){
add(LL(i) , RR(j) ^ 1) ;
add(RR(j) , LL(i) ^ 1) ;
}
if(getdis(RR(i) , LL(j)) < mid){
add(RR(i) , LL(j) ^ 1) ;
add(LL(j) , RR(i) ^ 1) ;
}
if(getdis(RR(i) , RR(j)) < mid){
add(RR(i) , RR(j) ^ 1) ;
add(RR(j) , RR(i) ^ 1) ;
}
}
}
}
void tarjan(int now){
dfn[now] = low[now] = ++ dp ;
st[top ++] = now ;
inst[now] = 1 ;
for (int i = head[now] ; ~i ; i = ed[i].next ){
int e = ed[i].e ;
if(!dfn[e]){
tarjan(e) ;
low[now] = min(low[now] , low[e]) ;
}
else if(inst[e]){
low[now] = min(low[now] , dfn[e]) ;
}
}
if(low[now] == dfn[now]){
ca ++ ;
int xx ;
do{
xx = st[-- top] ;
belong[xx] = ca ;
inst[xx] = 0 ;
}while(xx != now) ;
}
}
int doit(){
for (int i = 0 ; i < n << 1 ; i ++ )if(!dfn[i])tarjan(i) ;
for (int i = 0 ; i < n ; i ++ )if(belong[LL(i)] == belong[RR(i)])return 0 ;
return 1 ;
}
int main() {
while(cin >> n ){
for (int i = 0 ; i < n ; i ++ ){
cin >> x[LL(i)] >> y[LL(i)] ;
cin >> x[RR(i)] >> y[RR(i)] ;
}
double l = 0 , r = 30000 ,mid ;
while(r - l > 1e-4){
mid = (l + r) / 2 ;
build(mid) ;
if(doit())l = mid ;
else r = mid ;
}
printf("%.2f\n",mid / 2) ;
}
return 0 ;
}