題意：
? ? ? 給n個點，每個點必須在一個正方形上，可以在正方向上面邊的中點或者是下面邊的中點，正方形是和x,y軸平行的，而且所有的點的正方形的邊長一樣，并且正方形不能相互重疊（邊相鄰可以），問滿足這個要求的正方形的最大邊長是多少？


思路：

? ? ? 點的個數最少是3，所以不存在無窮大的情況，每個點的正方形有兩種選擇，所以是兩種中選一種，每兩個點中可能存在某種選擇和某種選擇沖突的情況，那么好辦了，是不是就是夫妻參加晚會只能去一個但是一些人之間有矛盾不能同時去的變形？直接就是2-sat，至于答案是輸出最大的邊長，這個好辦，直接二分邊長，然后每一步都是2-sat判斷是否可行就ok了。

#include<stack> #include<stdio.h> #include<string.h>#define N_node 200 + 10 #define N_edge 100000 + 100using namespace std;typedef struct {int to ,next; }STAR;typedef struct {double x ,y; }NODE;NODE node[N_node]; STAR E1[N_edge] ,E2[N_edge]; int list1[N_node] ,list2[N_node] ,tot; int Belong[N_node] ,mark[N_node] ,CNT; stack<int>mysk;void add(int a ,int b) {E1[++tot].to = b;E1[tot].next = list1[a];list1[a] = tot;E2[tot].to = a;E2[tot].next = list2[b];list2[b] = tot; }void DFS1(int s) {mark[s] = 1;for(int k = list1[s] ;k ;k = E1[k].next){int to = E1[k].to;if(!mark[to]) DFS1(to);}mysk.push(s); }void DFS2(int s) {Belong[s] = CNT;mark[s] = 1;for(int k = list2[s] ;k ;k = E2[k].next){int to = E2[k].to;if(!mark[to]) DFS2(to);} }double minn(double x ,double y) {return x < y ? x : y; }double maxx(double x ,double y) {return x > y ? x : y; }bool jude(NODE a ,NODE b ,double l) {double s ,x ,z ,y;s = minn(a.y + l ,b.y + l);y = minn(a.x + l ,b.x + l);x = maxx(a.y ,b.y);z = maxx(a.x ,b.x);return s > x && y > z;}bool J(int n ,int nowl) {int i ,j ,a1 ,a2 ,b1 ,b2;NODE t1 ,t2;double r = nowl * 1.0 / 2;memset(list1 ,0 ,sizeof(list1));memset(list2 ,0 ,sizeof(list2));tot = 1;for(i = 1 ;i <= n ;i ++)for(j = i + 1 ;j <= n ;j ++){a1 = i * 2 ,b1 = i * 2 + 1;a2 = j * 2 ,b2 = j * 2 + 1;//上上t1.x = node[i].x - r ,t1.y = node[i].y;t2.x = node[j].x - r ,t2.y = node[j].y;if(jude(t1 ,t2 ,nowl * 1.0)) add(a1 ,a2 ^ 1) ,add(a2 ,a1 ^ 1);//上下t1.x = node[i].x - r ,t1.y = node[i].y;t2.x = node[j].x - r ,t2.y = node[j].y - r * 2;if(jude(t1 ,t2 ,nowl * 1.0)) add(a1 ,b2 ^ 1) ,add(b2 ,a1 ^ 1);//下上t1.x = node[i].x - r ,t1.y = node[i].y - r * 2;t2.x = node[j].x - r ,t2.y = node[j].y;if(jude(t1 ,t2 ,nowl * 1.0)) add(b1 ,a2 ^ 1) ,add(a2 ,b1 ^ 1);//下下t1.x = node[i].x - r ,t1.y = node[i].y - r * 2;t2.x = node[j].x - r ,t2.y = node[j].y - r * 2;if(jude(t1 ,t2 ,nowl * 1.0)) add(b1 ,b2 ^ 1) ,add(b2 ,b1 ^ 1);}memset(mark ,0 ,sizeof(mark));while(!mysk.empty()) mysk.pop();n *= 2;for(i = 1 ;i <= n ;i ++)if(!mark[i]) DFS1(i);CNT = 0;memset(mark ,0 ,sizeof(mark));while(!mysk.empty()){int xin = mysk.top();mysk.pop();if(mark[xin]) continue;CNT ++;DFS2(xin);}int mk = 0;for(i = 1 ;i <= n ;i += 2)if(Belong[i] == Belong[i^1]){mk = 1;break;}return !mk; }int main () {int t ,n ,i ,j;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);for(i = 1 ;i <= n ;i ++)scanf("%lf %lf" ,&node[i].x ,&node[i].y);int low = 0 ,up = 20000 + 100 ,mid ,ans = 0;while(low <= up){mid = (low + up) >> 1;if(J(n ,mid)) ans = mid ,low = mid + 1;else up = mid - 1;}printf("%d\n" ,ans);}return 0; }

總結

以上是生活随笔為你收集整理的POJ2296二分2sat的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。