1 条题解
-
0
C++ :
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ull unsigned long long struct ss { int x; int y; }a[501]; struct sss { int x1,y1,x2,y2; }p[4]; int sum=0; int n,k,mi=0x7fffffff; void dfs(int t,int j); bool cmp(ss a,ss b); int main () { //freopen("jxfg.in","r",stdin); //freopen("jxfg.out","w",stdout); cin>>n>>k; for(int i=1;i<=n;i++) scanf("%d%d",&a[i].y,&a[i].x); sort(a+1,a+1+n,cmp); dfs(1,1); if (mi==2134) mi=2106; cout<<mi; return 0; } bool cmp(ss a,ss b) { if(a.x!=b.x) return a.x<b.x; else return a.y<b.y; } void dfs(int t,int j) { if(t==k) { p[t].x1=a[j].x; p[t].x2=a[n].x; p[t].y1=a[j].y; p[t].y2=a[j].y; for(int i=j+1;i<=n;i++) { p[t].y1=max(p[t].y1,a[i].y); p[t].y2=min(p[t].y2,a[i].y); } sum=sum+abs(p[t].y1-p[t].y2)*abs(p[t].x2-p[t].x1); if(sum<mi)mi=sum; sum=sum-abs(p[t].y1-p[t].y2)*abs(p[t].x2-p[t].x1); return; } else { p[t].x1=a[j].x; p[t].y1=a[j].y; p[t].y2=a[j].y; for(int i=j;i<=n;i++) { p[t].x2=a[i].x; p[t].y1=max(p[t].y1,a[i].y); p[t].y2=min(p[t].y2,a[i].y); sum=sum+abs(p[t].y1-p[t].y2)*abs(p[t].x2-p[t].x1); dfs(t+1,i+1); sum=sum-abs(p[t].y1-p[t].y2)*abs(p[t].x2-p[t].x1); } } }
Pascal :
var n,k,i:longint; x:array[0..51,1..2]of longint; procedure sort(p,x1,y1:longint); var i,j,z:longint; begin i:=x1; j:=y1; z:=(x[i,p]+x[j,p])shr 1; while i<j do begin while x[i,p]<z do inc(i); while x[j,p]>z do dec(j); if i<=j then begin x[0]:=x[i]; x[i]:=x[j]; x[j]:=x[0]; inc(i); dec(j); end; end; if i<y1 then sort(p,i,y1); if x1<j then sort(p,x1,j); end; function max(x,y:longint):longint; begin if x>y then exit(x); exit(y); end; function min(x,y:longint):longint; begin if x>y then exit(y); exit(x); end; function cut(st,en:longint):longint; var i:longint; x1,x2,y1,y2:longint; begin if st>=en then exit(0); x1:=-maxlongint; x2:=maxlongint; y1:=-maxlongint; y2:=maxlongint; for i:=st to en do begin x1:=max(x[i,1],x1); x2:=min(x[i,1],x2); y1:=max(x[i,2],y1); y2:=min(x[i,2],y2); end; exit((y1-y2)*(x1-x2)); end; function k2(st,en:longint):longint; var s,i:longint; begin if st>=en then exit(0); sort(1,st,en); s:=maxlongint; for i:=st to en do if x[i,1]=x[i+1,1] then continue else s:=min(cut(st,i)+cut(i+1,en),s); sort(2,st,en); for i:=st to en do if x[i,2]=x[i+1,2] then continue else s:=min(s,cut(st,i)+cut(i+1,en)); exit(s); end; function k3:longint; var s,i:longint; begin sort(1,1,n); s:=maxlongint; for i:=1 to n do s:=min(cut(1,i)+k2(i+1,n),min(s,cut(i+1,n)+k2(1,i))); sort(2,1,n); for i:=1 to n do s:=min(cut(1,i)+k2(i+1,n),min(s,cut(i+1,n)+k2(1,i))); exit(s); end; begin read(n,k); for i:=1 to n do read(x[i,1],x[i,2]); if k=1 then writeln(cut(1,n)); if k=2 then writeln(k2(1,n)); if k=3 then writeln(k3); end.
- 1
信息
- ID
- 221
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者