Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

HDU 1542 Atlantis ( Scanning Line, Segment Tree )

Problem - 1542題意: 給很多矩形的左下角和右上角座標,問聯集面積為何。資料規模: 座標為有理數 N ≤ 100解法: 離散化座標後,由下到上推移掃描線。時間 / 空間複雜度: O( N lg^2 N ) / O( N lg N ) #include <bits/stdc++.h> using namespace std; const int MAXN = 10</bits/stdc++.h>…

IOI 1998 Picture ( Scanning Line, Segment Tree )

PEG Judge - IOI '98 - Picture題意: 給很多矩形的左下角和右上角座標,問總周長為何。被包含的線段不算在周長裡。資料規模: The first line of the input contains the number of rectangles (0 ≤ number of rectangles 解法: 掃描線,考慮對 X, Y 方向…

CFR 337 D. Vika and Segments ( = 矩形面積 Segment Tree + Scanning Line )

Problem - D - Codeforces 事實上應該有更好的解法,就是先把所有矩形的面積取和,再用BIT之類的結構維護一些東西,計算所有重疊的部分然後減去。但顯然也能直接當作是矩形面積覆蓋問題。因為後者比較有實用性,而且自己不太熟悉,我試著實現了後者。這是一…

CFR Educational 10 D. Nested Segments ( Segment Tree + Scanning Line )

Problem - D - Codeforces Sort by left bound, that scan from left to right, we will query the number of right bounds that are before the right bound of the current segment. After answering the query, the segment should be removed, which wil…