POJ2296 Map Labeler

2022-09-23 02:02:08 字數 1041 閱讀 4357

一個平面直角座標系裡有 \(n\) 個點,要求使這些點每一個都在一個具有一定長度的正方形的上邊或下邊(正方形不能重合,邊界可以重疊),求這個正方形的最大邊長。

注意:這道題每個點先輸入的是縱座標,其次才是橫座標。

首先顯然正方形邊長滿足單調性,所以二分最大邊長 \(mid\)。

考慮如何判定一個答案是否合法,如果兩個點 \(a,b\) 滿足 \(|a_y-b_y|,那麼這兩個點放正方形就會有影響。

由於每個點放正方形的方案就只有兩種,所以考慮變成 2-sat 問題。設 \(a\) 表示點 \(a\) 的正方形往上放,\(a+n\) 表示 \(a\) 的正方形往下放。

設 \(a_x\geq b_x\):

#include #include #include #include using namespace std;

const int n=210;

int t,n,tot,cnt,head[n],dfn[n],low[n],col[n];

bool vis[n];

stackst;

struct node

a[n];

struct edge

e[n*n*4];

void add(int from,int to)

void tarjan(int x)

else if (vis[v])

low[x]=min(low[x],dfn[v]);

} if (dfn[x]==low[x])

while (x!=y); }}

bool check()

int binary()

tot=cnt=0;

for (int i=1;i<=n*2;i++)

if (!dfn[i]) tarjan(i);

if (check()) l=mid+1;

else r=mid-1;

} return l-1;

}int main()

return 0;

}

POJ 2296 Map Labeler

題意 題意 給你n個點,每個點上都放一個正方形,點只能在正方形的上邊或下邊的中點上,所有正方形大小一樣,不能有面積重疊,求最大的正方形。 n 100 include include include include include using namespace std const int n 100...

POJ 2503 Babelfish map

題目傳送門 題目中文翻譯 description 你剛從滑鐵盧搬到了一個大城市。這裡的人們說的是一種難以理解的外語方言。幸運的是,你有一本詞...

POJ 3320 尺取法,Hash,map標記

1 poj 3320 3 總結 尺取法,hash,map標記 看書複習,p頁書,一頁有一個知識點,連續看求最少多少頁看完所有知識點 必須說,...