1 条题解

  • 0
    @ 2021-6-14 23:29:28

    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
    上传者