本文共 2093 字，大约阅读时间需要 6 分钟。
【题目链接】
【题目大意】
坐标轴上有N个点，要在每个点上贴一个正方形，这个正方形的横竖边分别和x，y轴平行，并且要使得点要么在正方形的上面那条边的中点，或者在下面那条边的中点，并且任意两个点的正方形都不重叠（可以重边）。问正方形最大边长可以多少？
【思路】
可以很容易的看出，正方形要么在点的上方，要么在下方，所以是用2-SAT来判断的，关键是加边的判断，要涉及到两个正方形的位置的重叠关系比较麻烦。
然后二分正方形的边长即可。
【代码】
#include #include #include #include using namespace std;const int MAXN = 110;const int VN = MAXN*2;const int EN = VN*VN*2*10;const int INF = 0x3f3f3f3f;int n;int Abs(int n){ return n<0?-n:n;}struct Node{ int x, y;}arr[MAXN];struct Graph{ int size, head[VN]; struct{int v, next; }E[EN]; void init(){size=0; memset(head, -1, sizeof(head)); }; void addEdge(int u, int v){ E[size].v = v; E[size].next = head[u]; head[u] = size++; }}g;class Two_Sat{public: bool check(const Graph& g, const int n){ scc(g, 2*n); for(int i=0; i = r) continue; if(Abs(arr[i].y-arr[j].y) >= 2*r) continue; if(Abs(arr[i].y-arr[j].y) < r){ if(arr[i].y > arr[j].y){ // i在上面 g.addEdge(i, j+n); g.addEdge(i+n, i); g.addEdge(j, j+n); g.addEdge(j+n, i); }else if(arr[i].y < arr[j].y){ g.addEdge(j, i+n); g.addEdge(j+n, j); g.addEdge(i, i+n); g.addEdge(i+n, j); }else{ g.addEdge(i, j+n); g.addEdge(i+n, j); g.addEdge(j, i+n); g.addEdge(j+n, i); } }else{ if(arr[i].y > arr[j].y){ g.addEdge(i+n, j+n); g.addEdge(j, i); }else{ g.addEdge(j+n, i+n); g.addEdge(i, j); } } } }}int main(){ int nCase; scanf("%d", &nCase); while(nCase--){ scanf("%d", &n); for(int i=0; i >1; buildGraph(m); if(sat.check(g, n)){ ans = m; l=m+1; } else r=m; } printf("%d\n", ans); } return 0;}
转载地址：http://spzni.baihongyu.com/