第四題矩形覆蓋
矩形覆蓋（存檔名noipg4）
[問題描述]:
在平面上有 n 個點（n <= 50），每個點用一對整數座標表示。例如：當 n＝4 時，4個點的座標分另為：
p1（1，1），p2（2，2），p3（3，6），p4（0，7），見圖一。
這些點可以用 k 個矩形（1<=k<=4）全部覆蓋，矩形的邊平行於座標軸。當 k=2 時，可用如圖二的兩個矩形 sl，s2 覆蓋，s1，s2 面積和為 4。問題是當 n 個點座標和 k 給出後，怎樣才能使得覆蓋所有點的 k 個矩形的面積之和為最小呢。
約定：覆蓋乙個點的矩形面積為 0；覆蓋平行於座標軸直線上點的矩形面積也為0。各個矩形必須完全分開（邊線與頂點也都不能重合）。
[輸入]:
鍵盤輸人檔名。檔案格式為
n kxl y1
x2 y2
xn yn （0<=xi,yi<=500)
[輸出]:
輸出至螢幕。格式為：
乙個整數，即滿足條件的最小的矩形面積之和。
[輸入輸出樣例]
: 4 2
1 12 23 60 7螢幕顯示：4分析
【題解一】
1、本題的難度較大。如果你這樣認為：即在假定已用i個矩形（面積和滿足最小）覆蓋所有點的基礎上，窮舉所有2個矩形合併成1個矩形（條件是：
在所有合併方案中使合併後面積最小），從而使矩形個數減少為i-1——那就錯了，可是卻可以通過前4組測試資料！
正確的做法是對不同的k值分別進行計算，好在k值較小，否則...
討論：k=1，只要求出n個點座標的最大、最小值，就可求得矩形的位置與面積；
k=2，有2個矩形，它們只有2種分布形式：左右式（flag=0），上下式（flag=1）
對於左右式，顯然要先將所有點按橫座標公升序排列，可將點1~點i-1放入矩形1中，將點i~點n放入矩形2中，求兩矩形的面積之和；如果面積和比上乙個值小，記下；讓i從2迴圈到n,就可完成左右式的全部搜尋；
對於上下式，先將所有點按縱座標公升序排列，依此類推。
k=3，有3個矩形，它們有6種分布形式：
要用兩重迴圈進行搜尋：設i,j為迴圈變數，將點1~i-1放入矩形1中，點i~j-1放入矩形2中，點j~n放入矩形3中；點必須在放入前排好序（均為公升序）：對於flag=0,所有點按橫座標排序；對於flag=1,所有點按縱座標排序；對於flag=2,所有點先按橫座標排序，然後點i~n按縱座標排序；對於flag=3,所有點先按橫座標排序，然後點1~j-1按縱座標排序；對於flag=4,所有點先按縱座標排序，然後點1~j-1按橫座標排序；對於flag=5,所有點先按縱座標排序，然後點i~n按橫座標排序；
至於k=4,4個矩形有22種分布形式，實在太複雜！幸好測試資料中沒有k=4的情形(似乎有意放了一馬？)。據說本題全國沒有一人全對！（只要求k=1，2，3）
程式清單
program noipg4;
const maxn=50;maxk=3;
type rect=record
l,r,t,b:word;
end;
vxy=record
x,y:word;
end;
var ju:array[1..maxk]of rect;
v:array[1..maxn,0..2] of vxy;v0:vxy;
n,k,i,j,ii,jj:byte;f:text;filename:string;
smin,temp:longint;
function intersect(jui,juj:rect):boolean;
var b1,b2,t1,t2,l1,l2,r1,r2:word;
begin
b1:=
l1:=
intersect:=((l2<=r1) and (l2>=l1) or (r2<=r1) and (r2>=l1) or (l2<=l1)
and (r2>=r1)) and ((t2<=b1) and (t2>=t1) or (b2<=b1) and (b2>=t1)
or (b2>=b1) and (t2<=t1));
end;
function area(ju:rect):longint;
var temp:longint;
begin
temp:=
end;
procedure insert(v:vxy;var ju:rect);
begin
if < then
if > then
if < then
if > then
end;
procedure init;
begin
write('input filename:');readln(filename);
assign(f,filename);reset(f);readln(f,n,k);
for i:=1 to n do begin
read(f,v[i,0].x,v[i,0].y);
v[i,1].x:=v[i,0].x;v[i,1].y:=v[i,0].y;
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if v[i,0].x>v[j,0].x then begin
v0:=v[i,0];v[i,0]:=v[j,0];v[j,0]:=v0;
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if v[i,1].y>v[j,1].y then begin
v0:=v[i,1];v[i,1]:=v[j,1];v[j,1]:=v0;
end;
end;
procedure solve;
begin
smin:=maxlongint;
case k of
1:begin
ju[1].b:=v[n,1].y;ju[1].t:=v[1,1].y;
ju[1].r:=v[n,0].x;ju[1].l:=v[1,0].x;
smin:=area(ju[1]);
end;
2:for jj:=0 to 1 do begin
flag=0,1的情形}
ju[1].b:=v[1,jj].y;ju[1].t:=v[1,jj].y;
ju[1].r:=v[1,jj].x;ju[1].l:=v[1,jj].x;
for i:=2 to n do begin
insert(v[i-1,jj],ju[1]);
ju[2].b:=v[i,jj].y;ju[2].t:=v[i,jj].y;
ju[2].r:=v[i,jj].x;ju[2].l:=v[i,jj].x;
for ii:=i+1 to n do insert(v[ii,jj],ju[2]);
if not intersect(ju[1],ju[2]) then begin
temp:=0;for ii:=1 to k do temp:=temp+area(ju[ii]);
if tempend;
end;
end;
3:begin
for jj:=0 to 1 do begin
ju[1].b:=v[1,jj].y;ju[1].t:=v[1,jj].y;
ju[1].r:=v[1,jj].x;ju[1].l:=v[1,jj].x;
for i:=2 to n-1 do begin
insert(v[i-1,jj],ju[1]);
ju[2].b:=v[i,jj].y;ju[2].t:=v[i,jj].y;
矩形菱形證明
矩形的定義與判定講義 學生 年級 初二教師 周金金科目 數學班主任 黃老師時間 一 知識回顧 1 平行四邊形的判定方法 2 矩形的性質 3 矩形的判定 典型例題 1 在矩形中，平分，過點作於，延長 交於點，下列結論中 正確的 abcd 1題2題3題 2 2014山東聊城，第9題，3分 如圖，在矩形a...
矩形經典例題
一 計算 1 已知矩形的對角線長為1，兩條相鄰邊之和為m，求矩形的面積 解析 依題設畫出示意圖，由矩形性質 又 由有 評述1 矩形作為特殊的平行四邊形其最特殊之處在於4個內角均為90 稍加鏈結，則會出現rt 借助勾股定理，矩形中只要知道一些條件 面積 邊長等皆可計算 評述2 此處兼顧考查了整式運算技...
矩形專項訓練
學校班級姓名座號 評分 1 如圖，矩形abcd中，ac與bd交於o點，於e，於f。求證 be cf。2 如圖所示，e為 abcd外，ae ce,be de，求證 abcd為矩形 3 如圖，矩形abcd的對角線相交於點o，of bc，ce bd，oe be 1 3，of 4，求 adb的度數和bd的長...