【题目描述】 农夫约翰有N（5<=N<=50000）头牛在牧场里吃草。现在约翰买了一个栅栏把它们围在一起（奶牛在栅栏上也视为被围住）。这个栅栏是长方形的，边都平行于X轴和Y轴。为了让它们吃的好一些，这个栅栏应该尽可能小。为了达到这个目的，约翰可以把三头奶牛挑出牧场，这三头牛约翰可以任意选择。现在约翰想知道栅栏围成的最小面积。 【输入格式】 第一行一个整数N表示有N头奶牛 接下来N行，每行两个正整数x和y表示每头奶牛的位置，横纵坐标均在1至40000之间 【输出格式】 一个整数表示去掉3头牛后栅栏的最小面积 【样例输入】 6 1 1 7 8 10 9 8 12 4 100 50 7 【样例输出】 12 【样例说明】 去掉(1,1),(4,100),(50,7)即可。 【分析】 不难发现最优解肯定是去除了最外面那一层的，因为去除中间的奶牛的话栅栏还是那么长。于是可以搜索出去掉外面三层之后的栅栏长度并打擂台。
type rec=record x,y,z:longint; end; var a,b:array[0..50001]of rec; v:array[0..50001]of boolean; i,n:longint; ans:int64; procedure qsort1(l,r:longint); var i,j,mid:longint; temp:rec; begin i:=l; j:=r; mid:=a[(l+r) div 2].x; repeat while a[i].x<mid do inc(i); while a[j].x>mid do dec(j); if i<=j then begin temp:=a[i];a[i]:=a[j];a[j]:=temp; inc(i);dec(j); end; until i>j; if l<j then qsort1(l,j); if i<r then qsort1(i,r); end; procedure qsort2(l,r:longint); var i,j,mid:longint; temp:rec; begin i:=l; j:=r; mid:=b[(l+r) div 2].y; repeat while b[i].y<mid do inc(i); while b[j].y>mid do dec(j); if i<=j then begin temp:=b[i];b[i]:=b[j];b[j]:=temp; inc(i);dec(j); end; until i>j; if l<j then qsort2(l,j); if i<r then qsort2(i,r); end; function min(x,y:int64):int64; begin if x<y then exit(x) else exit(y); end; procedure search(xx:longint); var i:longint; minx,miny,maxx,maxy:int64; begin for i:=1 to n do begin minx:=a[i].x;if not v[a[i].z] then break; end; for i:=n downto 1 do begin maxx:=a[i].x;if not v[a[i].z] then break; end; for i:=1 to n do begin miny:=b[i].y;if not v[b[i].z] then break; end; for i:=n downto 1 do begin maxy:=b[i].y;if not v[b[i].z] then break; end; ans:=min(ans,(maxx-minx)*(maxy-miny)); if xx=3 then exit; for i:=1 to n do if not v[a[i].z] then begin v[a[i].z]:=true;search(xx+1);v[a[i].z]:=false;break; end; for i:=n downto 1 do if not v[a[i].z] then begin v[a[i].z]:=true;search(xx+1);v[a[i].z]:=false;break; end; for i:=1 to n do if not v[b[i].z] then begin v[b[i].z]:=true;search(xx+1);v[b[i].z]:=false;break; end; for i:=n downto 1 do if not v[b[i].z] then begin v[b[i].z]:=true;search(xx+1);v[b[i].z]:=false;break; end; end; begin fillchar(v,sizeof(v),false); readln(n); for i:=1 to n do begin readln(a[i].x,a[i].y); a[i].z:=i; b[i]:=a[i]; end; qsort1(1,n); qsort2(1,n); ans:=maxlongint; search(0); write(ans); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533497.html
