알고리즘 sorting, segtree 시간복잡도 $O(NlogN)$ 풀이 한 가로선 또는 세로선 기준으로 두 직사각형이 구분됨이 보장됨. WLOG 자르는 선을 세로선이라 하면, 각 직사각형당 가로 길이: 미리 sort 해놓은 배열에서의 차, $O(1)$ 세로 길이: 구간에서의 $max-min$, segment tree로 $O(logN)$ (구간이 시작 또는 끝을 포함하므로 prefix/suffix max/min으로도 가능) 코드 #include using namespace std; #define ll long long int N; pair a[50005]; ll x[50005], y[50005], befans, ans = 1e18; struct z { ll mx, mn; }; z xtree[200005..
