自动搬运

查看原文

来自洛谷，原作者为

	Up_Xu **

搬运于2025-08-24 22:16:19，当前版本为作者最后更新于2023-08-14 20:55:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给出 $n$ 个制镜厂各自所能制造镜子的最小宽度、最大宽度、最小高度、最大高度， 求是否有制镜厂能制出所有其它制镜厂能制出的镜子。

思路

若有一家制镜厂 $i$ 能制出所有其它制镜厂能制出的镜子，就说明此制镜厂所制镜子的最小宽度 $w1_i$ 为所有厂制镜最小宽度的最小值，最大宽度 $w2_i$ 为所有厂制镜最大宽度的最大值，最小高度 $h1_i$ 为所有厂制镜最小高度的最小值，最大高度 $h2_i$ 为所有厂制镜最大高度的最大值。

这么一想，本题就超级简单了。求出所有制镜厂制镜最小宽度的最小值 $mw1$，制镜最大宽度的最大值 $mw2$，制镜最小高度的最小值 $mh1$，以及制镜最大高度的最大值 $mh2$。然后枚举每家制镜厂，看是否有一家的最小宽度与 $mv1$ 相等，最大宽度与 $mv2$ 相等，最小高度与 $mh1$ 相等，最大高度与 $mh2$ 相等即可。

代码

#include <bits/stdc++.h>
#define M 100010
using namespace std;
int T,n;
int w1[M],w2[M],h1[M],h2[M],mw1,mh1,mw2,mh2;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);//加速代码 
	cin>>T;
	while(T--){
		cin>>n;
		mw1=mh1=1e9;mw2=mh2=0;//先赋上最大值与最小值 
		for(int i=1;i<=n;i++){
			cin>>w1[i]>>w2[i]>>h1[i]>>h2[i];
			mw1=min(mw1,w1[i]);//求最小宽度的最小值
			mw2=max(mw2,w2[i]);//求最大宽度的最大值
			mh1=min(mh1,h1[i]);//求最小高度的最小值
			mh2=max(mh2,h2[i]);//求最大高度的最大值
		}
		int flag=1;
		for(int i=1;i<=n;i++)
			if(w1[i]==mw1&&w2[i]==mw2&&h1[i]==mh1&&h2[i]==mh2){//判断是否都相等 
				cout<<"TAK\n";
				flag=0;
				break;
			}
		if(flag)cout<<"NIE\n";
	}
}