【BZOJ3571】【HNOI2014】画框

久闻公之大名

大概就是把每个结果看成坐标为\(\sum a,\sum b\)的点，那么答案一定在这些点的左下凸壳上。

为了勾勒出凸包，我们可以先找到最左边和最下面的两个点，然后每次找到离当前两个点连线最远的点并分两边递归向下。

要找到最远的点，只要算出每个\(a,b\)的截距，那么只要截距最小即可。这个可以用KM算法来求。

// <3571.cpp> - Thu Feb 23 09:48:59 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <complex>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
typedef complex<int> pt;
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int N=75;
const int INF=1e9;
#define forall() for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
int n,a[N][N],b[N][N],w[N][N];
int lx[N],ly[N],slack[N],mat[N];
bool vx[N],vy[N];
bool dfs(int x){
    vx[x]=1;
    for(int i=1;i<=n;i++){
        if(vy[i])continue;
        int k=lx[x]+ly[i]-w[x][i];
        if(!k){
            vy[i]=1;
            if(!mat[i]||dfs(mat[i]))return mat[i]=x;
        }else slack[i]=min(slack[i],k);
    }
    return 0;
}
pt km(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)lx[i]=max(lx[i],w[i][j]);
        ly[i]=mat[i]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)slack[j]=INF,vx[j]=vy[j]=0;
        while(!dfs(i)){
            int d=INF;
            for(int j=1;j<=n;j++)if(!vy[j])d=min(d,slack[j]);
            for(int j=1;j<=n;j++)if(vx[j])lx[j]-=d;
            for(int j=1;j<=n;j++)if(vy[j])ly[j]+=d;
            for(int j=1;j<=n;j++)vx[j]=vy[j]=0;
        }
    }
    int ta=0,tb=0;
    for(int i=1;i<=n;i++)ta+=a[mat[i]][i],tb+=b[mat[i]][i];
    return pt(ta,tb);
}
int work(pt l,pt r){
    forall()w[i][j]=a[i][j]*(r.imag()-l.imag())-b[i][j]*(r.real()-l.real());
    pt m=km();
    if(l==m||m==r)return min(l.real()*l.imag(),r.real()*r.imag());
    return min(work(l,m),work(m,r));
}
int main(){
    int T=gi();
    while(T--){
        n=gi();
        forall()a[i][j]=gi();
        forall()b[i][j]=gi();
        forall()w[i][j]=-a[i][j];
        pt l=km();
        forall()w[i][j]=-b[i][j];
        pt r=km();
        printf("%d\n",work(l,r));
    }
    return 0;
}

// <3571.cpp> - Thu Feb 23 09:48:59 2017

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <complex>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

typedef complex<int> pt;

template<typename T>

inline void gg(T &res){

res=0;T fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

res*=fh;

}

inline int gi(){int x;gg(x);return x;}

inline lol gl(){lol x;gg(x);return x;}

const int N=75;

const int INF=1e9;

#define forall() for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)

int n,a[N][N],b[N][N],w[N][N];

int lx[N],ly[N],slack[N],mat[N];

bool vx[N],vy[N];

bool dfs(int x){

vx[x]=1;

for(int i=1;i<=n;i++){

if(vy[i])continue;

int k=lx[x]+ly[i]-w[x][i];

if(!k){

vy[i]=1;

if(!mat[i]||dfs(mat[i]))return mat[i]=x;

}else slack[i]=min(slack[i],k);

}

return 0;

}

pt km(){

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++)lx[i]=max(lx[i],w[i][j]);

ly[i]=mat[i]=0;

}

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++)slack[j]=INF,vx[j]=vy[j]=0;

while(!dfs(i)){

int d=INF;

for(int j=1;j<=n;j++)if(!vy[j])d=min(d,slack[j]);

for(int j=1;j<=n;j++)if(vx[j])lx[j]-=d;

for(int j=1;j<=n;j++)if(vy[j])ly[j]+=d;

for(int j=1;j<=n;j++)vx[j]=vy[j]=0;

}

int ta=0,tb=0;

for(int i=1;i<=n;i++)ta+=a[mat[i]][i],tb+=b[mat[i]][i];

return pt(ta,tb);

}

int work(pt l,pt r){

forall()w[i][j]=a[i][j]*(r.imag()-l.imag())-b[i][j]*(r.real()-l.real());

pt m=km();

if(l==m||m==r)return min(l.real()*l.imag(),r.real()*r.imag());

return min(work(l,m),work(m,r));

}

int main(){

int T=gi();

while(T--){

n=gi();

forall()a[i][j]=gi();

forall()b[i][j]=gi();

forall()w[i][j]=-a[i][j];

pt l=km();

forall()w[i][j]=-b[i][j];

pt r=km();

printf("%d\n",work(l,r));

}

return 0;

}