白金元首与克劳德斯

输入的第一行包含一个正整数 T —— 数据的组数。接下来包含 T组数据，格式如下，数据间没有空行。
第 1 行：一个正整数 n —— 云朵的数量。
接下来 n 行：每行五个空格分隔的整数 x_i,y_i,w_i,h_i,d_i—— 描述一朵云在时刻 0的状态。

C++(clang++11) 解法, 执行用时: 904ms, 内存消耗: 6036K, 提交时间: 2021-01-29 21:59:13

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef struct n
{
	 int x,y,w,h;
	 int l,r;
};
int cmp(n x,n y)
{
	  return x.l<y.l;
}
n lef[maxn];
n up[maxn];
int leff=0;
int upp=0;
int main()
{
	int t;
	int x,y,w,h,d;
	int k;
	int q=0;
	cin>>t;
	for(int i=0;i<t;i++)
	{
		cin>>k;
		q=0;
		leff=0;
		upp=0;
		for(int j=0;j<k;j++)
		{
			 scanf("%d%d%d%d%d",&x,&y,&w,&h,&d);
			 if(d==0)
			  {
			  	 lef[leff]=(n){x,y,w,h,x+y,x+y+w+h};
			  	 leff++;
			  }
			  else if(d==1)
			  {
			  	 up[upp]=(n){x,y,w,h,x+y,x+y+w+h};
			  	 upp++;
			  }
		}
		sort(lef,lef+leff,cmp);
		sort(up,upp+up,cmp);
		for(int j=0,k=0;j<leff;j++)
		{
			
			 while(k<upp&&up[k].l<lef[j].l) k++;
			 if(k>=upp) break;
			 if(up[k].l<lef[j].r) 
			 {
			 	 q=1;
			 	 break;
			 }
		}
		
		for(int j=0,k=0;j<upp;j++)
		{
			
			 while(k<leff&&lef[k].l<up[j].l) k++;
			 if(k>=leff) break;
			 if(up[j].r>lef[k].l) 
			 {
			 	 q=1;
			 	 break;
			 }
		}
		if(q)
		   printf("2\n");
		else
		   printf("1\n");
	}
	
	
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 1076ms, 内存消耗: 2576K, 提交时间: 2020-07-04 09:57:03

#include <cstdio>
#include <algorithm>
int n, sum[2], T, X, Y, U, V, D, tot;
struct cyc
{
    int x, d, k;
} a[200010];
bool cmp(cyc a, cyc b) { return a.x < b.x || (a.x == b.x && a.k < b.k); }
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        tot = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d%d%d%d", &X, &Y, &U, &V, &D);
            a[++tot] = (cyc){X + Y, D, 1};
            //线段开始 +1
            a[++tot] = (cyc){X + Y + U + V, D, -1};
            //线段结束 -1
        }
        std::sort(a + 1, a + tot + 1, cmp);
        sum[0] = sum[1] = 0;
        int ans = 1;
        for (int i = 1; i <= tot; i++)
        {
            sum[a[i].d] += a[i].k;
            if (sum[0] && sum[1])
            {
                ans = 2;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

详情