题目描述 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.
输入 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.
输出 For each test case, print a single line containing an integer, denoting the minimum number of steps.
样例输入 1 2 2 2 3 3 4 4 5 5
样例输出 2
思路 与一个平面内所有矩形的距离之和最小的是所有x，y坐标值构成的中位点，由此即可得到答案
代码实现
#pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=200005; const int M=10005; const int INF=0x3f3f3f3f; const int mod=1000000007; typedef pair<int,int>P; struct node { ll x1,x2,y1,y2; }pt[N]; ll px[N],py[N]; int n; ll cal(node a,ll x,ll y) { ll sum=0; if(x<a.x1 || x>a.x2) sum+=min(abs(x-a.x1),abs(x-a.x2)); if(y<a.y1 || y>a.y2) sum+=min(abs(y-a.y1),abs(y-a.y2)); return sum; } int main() { int T; scanf("%d",&T); while(T--) { int cnt1=0,cnt2=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld%lld%lld%lld",&pt[i].x1,&pt[i].y1,&pt[i].x2,&pt[i].y2); px[++cnt1]=pt[i].x1;px[++cnt1]=pt[i].x2; py[++cnt2]=pt[i].y1;py[++cnt2]=pt[i].y2; } sort(px+1,px+cnt1+1); sort(py+1,py+cnt2+1); ll ans=0; for(int i=1;i<=n;i++) ans+=cal(pt[i],px[n],py[n]); printf("%lld\n",ans); } return 0; }