http://poj.org/problem?id=2296
題意：題意：給你n個點，每個點上都放一個正方形，點只能在正方形的上邊或下邊的中點上，所有正方形大小一樣，不能有面積重疊，求最大的正方形。（n<=100）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int N=100*2+10, M=N*N*4;
struct E { int next, to; }e[M];
int ihead[N], cnt, tot, num, vis[N], FF[N], LL[N], p[N], n, top, s[N], X[N], Y[N];
void add(int u, int v) { e[++cnt]=(E){ihead[u], v}; ihead[u]=cnt; }
void tarjan(int x) {FF[x]=LL[x]=++tot; vis[x]=1; s[++top]=x;for(int i=ihead[x]; i; i=e[i].next) {if(!FF[e[i].to]) tarjan(e[i].to), LL[x]=min(LL[x], LL[e[i].to]);else if(vis[e[i].to]) LL[x]=min(LL[x], FF[e[i].to]);}if(FF[x]==LL[x]) {int y;++num;do {y=s[top--];vis[y]=0;p[y]=num;} while(x!=y);}
}
void clr() {cnt=tot=num=top=0;int nn=n<<1;memset(ihead, 0, sizeof(int)*(nn));memset(p, 0, sizeof(int)*(nn));memset(FF, 0, sizeof(int)*(nn));
}
bool check(int r) {for(int i=0; i<n; ++i) {for(int j=i+1; j<n; ++j) {int a=i<<1, b=j<<1;if(abs(X[i]-X[j])>=r) continue;int dy=abs(Y[i]-Y[j]);if(dy==0) add(a, b^1), add(b, a^1), add(a^1, b), add(b^1, a);else if(dy<r) { if(Y[i]>Y[j]) add(a^1, a), add(b, b^1); else add(a, a^1), add(b^1, b); }else if(r<dy && dy<(r<<1)) { if(Y[i]>Y[j]) add(a^1, b^1), add(b, a); else add(a, b), add(b^1, a^1); }}}int nn=n<<1, flag=1;for(int i=0; i<nn; ++i) if(!FF[i]) tarjan(i);for(int i=0; i<nn; i+=2) if(p[i]==p[i|1]) { flag=0; break; }clr();return flag;
}
int main() {int T; scanf("%d", &T);while(T--) {scanf("%d", &n);for(int i=0; i<n; ++i) scanf("%d%d", &X[i], &Y[i]);int mid, l=0, r=40000;while(l<=r) {mid=(l+r)>>1;if(check(mid)) l=mid+1;else r=mid-1;}printf("%d\n", l-1);}return 0;
}
以后必須注意= =2sat的建圖非常容易出錯= =我就不說我一開始以為長度只能是偶數（即沒發現矩陣頂點可以不是整數頂點啊！！）= =，然后發現錯了以后發現我之前寫的每一個點構造兩個矩陣然后判交的算法double精度跪掉了= =我竟然還調了好久= =
poj1741，于是跪拜了別人的code...QAQ
然后發現直接討論每一種情況就行了= =
注意！在2-sat建圖時，一定要對每一個a與b的可能都排列出來然后一個個判斷！還有，如果一個點非選不可那么應該連邊(a', a)或(a, a')！一定切記！
然后我相信你們能處理好這些情況的= =所以我就不打算說了...（對于鍛煉自己非常有好處哦～...
