题目是要求最小乘积最小权匹配，
将一种方案看做一个二维点(x,y),x=a值的和，y=b值的和，所有方案中只有在下凸壳上的点才有可能成为最优解
首先要求出两端的方案l,r两个点
l就是a值的和最小的方案，
r就是b值的和最小的方案
然后递归work(l,r)即可得出所有在下凸壳上的点
work(l,r){
找到一个离lr这条直线最远的且靠近原点的点mid
如果l,mid,r构成下凸壳{
work(l,mid)
work(mid,r)
}
}
如何找mid？
把所有边边权设为(a[i],b[i])它lr直线垂线上的投影，再求普通的最小权匹配即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf=~0U>>2,N=150,M=100110;
struct P{int x,y;P(){x=y=0;}P(int _x,int _y){x=_x,y=_y;}P operator-(const P&a){return P(x-a.x,y-a.y);}}L,R;
inline int cross(P a,P b){return a.x*b.y-a.y*b.x;}
int n,m,i,j,w[N][N],wa[N][N],wb[N][N],test,ans;
int u[M],v[M],c[M],co[M],coa[M],cob[M],nxt[M],t,S,T,l,r,q[M],g[N],f[N],d[N];bool in[N];
inline void add(int x,int y,int z,int zo,int zoa,int zob){
u[++t]=x;v[t]=y;c[t]=z;co[t]=zo;coa[t]=zoa;cob[t]=zob;nxt[t]=g[x];g[x]=t;
u[++t]=y;v[t]=x;c[t]=0;co[t]=-zo;coa[t]=-zoa;cob[t]=-zob;nxt[t]=g[y];g[y]=t;
}
inline bool spfa(){
memset(d,127,sizeof d);d[S]=0;in[S]=1;l=r=M>>1;q[l]=S;
int x,i;
while(l<=r){
int x=q[l++];
if(x==T)continue;
for(i=g[x];i;i=nxt[i])if(c[i]&&co[i]+d[x]<d[v[i]]){
d[v[i]]=co[i]+d[x];f[v[i]]=i;
if(!in[v[i]]){
in[v[i]]=1;
if(d[v[i]]<d[q[l]])q[--l]=v[i];else q[++r]=v[i];
}
}
in[x]=0;
}
return d[T]<=inf;
}
inline P mincostflow(){
P p;t=1;S=0;T=n*2+1;
for(i=0;i<=T;i++)g[i]=in[i]=0;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)add(i,j+n,1,w[i][j],wa[i][j],wb[i][j]);
for(i=1;i<=n;i++)add(S,i,1,0,0,0),add(i+n,T,1,0,0,0);
while(spfa())for(i=T;i!=S;i=u[f[i]])--c[f[i]],++c[f[i]^1],p.x+=coa[f[i]],p.y+=cob[f[i]];
if(p.x*p.y<ans)ans=p.x*p.y;
return p;
}
void work(P l,P r){
P t=l-r;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)w[i][j]=cross(P(wa[i][j],wb[i][j]),t);
P mid=mincostflow();
if(cross(mid-l,r-mid)>0)work(l,mid),work(mid,r);
}
int solve(){
ans=~0U>>1;
scanf("%d",&n);
for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&wa[i][j]);
for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&wb[i][j]);
for(i=1;i<=n;i++)for(j=1;j<=n;j++)w[i][j]=wa[i][j];
L=mincostflow();
for(i=1;i<=n;i++)for(j=1;j<=n;j++)w[i][j]=wb[i][j];
R=mincostflow();
work(L,R);
printf("%d\n",ans);
}
int main(){
scanf("%d",&test);
while(test--)solve();
return 0;
}