Đề bài: http://vn.spoj.com/problems/VOMOVREC/
Thuật toán: Ta sẽ tìm kiếm nhị phân kết quả của bài toán. Với mỗi giá trị chia nhị phân V, ta sẽ “nở” các hình chữ nhật ra về bốn phía một độ dài bằng V. Lúc này điều kiện cần và đủ để tất cả các hình chữ nhật ban đầu có thể di chuyển với khoảng cách không quá V thỏa mãn yêu cầu là tất cả các hình chữ nhật đã được nở có phần giao. Điều kiện N hình chữ nhật có phần giao chung hay không là max(X1) < min(X2) và max(Y1) < min(Y2).
Code:
uses math; const fi='';//vomovrec.inp'; fo='';//vomovrec.out'; maxn=trunc(1e6); oo=trunc(1e9)*3; type rect = record x1,y1,x2,y2 : int64; end; var m,n,i,j : longint; a : array[1..maxn] of rect; d,c,g : int64; function ok(k : int64) : boolean; var i : longint; x,y,u,v : int64; begin x := a[1].x1 - k; y := a[1].y1 - k; u := a[1].x2 +k; v := a[1].y2 + k; for i := 2 to n do with a[i] do begin x := max(x, x1-k); y := max(y, y1-k); u := min(u, x2+k); v := min(v, y2+k); end; if (x<u) and (y<v) then exit(true) else exit(false); end; begin assign(input,fi);reset(input); assign(output,fo);rewrite(output); read(n); for i := 1 to n do with a[i] do begin read(x1,y1,x2,y2); end; d := 0; c := oo; g := (d+c) div 2; while (g<>c) and (g<>d) do begin if ok (g) then c := g else d := g; g := (d+c) div 2; end;if ok(d) then begin write(d); exit; end; writeln(c); close(input); close(output); end. |
Speak Your Mind