G - Radar Scanner

There are n rectangle radar scanners on the ground. The sides of them are all paralleled to the axes. The i-th scanner's bottom left corner is square (ai,bi) and its top right corner is square (ci,di)

. Each scanner covers some squares on the ground.

You can move these scanners for many times. In each step, you can choose a scanner and move it one square to the left, right, upward or downward.

 

Today, the radar system is facing a critical low-power problem. You need to move these scanners such that there exists a square covered by all scanners.

Your task is to minimize the number of move operations to achieve the goal.

Input

The first line of the input contains an integer T(1≤T≤1000)

, denoting the number of test cases.

In each test case, there is one integer n(1≤n≤100000)

in the first line, denoting the number of radar scanners.

For the next n

lines, each line contains four integers ai,bi,ci,di(1≤ai,bi,ci,di≤109,ai≤ci,bi≤di)

, denoting each radar scanner.

It is guaranteed that ∑n≤106

.

Output

For each test case, print a single line containing an integer, denoting the minimum number of steps.

Sample Input

Input

1
2
2 2 3 3
4 4 5 5

Output

2

题意：选一个格子，让它到所有矩形的总路程最小

思路：以前看到过一个题目，在一条直线上有n个点，让你在x轴选一个位置，使它到所有点的距离最小，这个题目的解法就是把所有点坐标排序后直接选第n/2个点的坐标。这个题目的解法可以拓展到二维平面，所有，本题解法就是把x轴坐标和y轴坐标都排序，都选第（2*n）/2个点，即（x[n],y[n]）,然后算一遍距离，就是答案;

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<set>
#include<map>
#include<string>
#include<string.h>
#include<math.h>
#define maxn 405000
#define ll long long
#include<vector>
#include<queue>
using namespace std;
struct node
{
    ll a,b,c,d;
} a[maxn];
ll js(node p,ll x,ll y)
{
    ll a=p.a,b=p.b,c=p.c,d=p.d;
    ll sum=0;
    if(x>c||x<a)
    {
        sum+=min(abs(x-a),abs(x-c));
    }
    if(y>d||y<b)
    {
        sum+=min(abs(y-b),abs(y-d));
    }
    return sum;
}
ll idx[maxn],idy[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int x1=0,y1=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld %lld %lld %lld",&a[i].a,&a[i].b,&a[i].c,&a[i].d);
            idx[++x1]=a[i].a;idx[++x1]=a[i].c;
            idy[++y1]=a[i].b;idy[++y1]=a[i].d;
        }
        sort(idx+1,idx+1+x1);
        sort(idy+1,idy+y1+1);
        ll sum=0,x=idx[n],y=idy[n];
        for(int i=1;i<=n;i++)
        {
            sum+=js(a[i],x,y);
        }
        printf("%lld\n",sum);
    }
}