题解 – [20231110NOIP模拟] Cloud

题目描述

在 xy- 直角坐标平面的天空中，有 n 片四边平行于坐标轴的矩形云朵。每一片云由一个五元组 (xi,yi,wi,hi,di) 表示，其中 (xi,yi) 为云左下角顶点的坐标，w_i 表示云在 x 轴方向的宽度，h_i 表示云在 y 轴方向的长度，di∈\lbrace 0,1\rbrace 为云的移动方向（0 为横向，1 为纵向）。具体来说，满足 d_i=0 的云沿 x 轴正方向以每秒 1 长度单位的速率不断移动，而满足 d_i=1 的云沿 y 轴正方向以每秒 1 长度单位的速率不断移动。

枪神发现，所有的云在此时没有重叠的面积。他将这个时刻记作时刻 0。他想知道，对于 (-∞,+∞) 中的任意时刻和平面上的任意一个点，最多可以同时被多少片云覆盖。一个点在某时刻被一朵云覆盖当且仅当这个点位于该时刻云朵所处矩形的内部（不含边界）。

数据范围：1 \leq T \leq 15 ，− 5 × 10^8 \leq x_i, y_i \leq 5 × 10^8，1 \leq w_i, h_i 5 × 10^8, d_i \in \lbrace 0,1\rbrace.

题解

首先我们注意到两个性质：

• 初始时所有云都不相交
• 所有云只有两种方向移动，且速度相同

那就可以考虑转化问题：固定向右移动的云，向上运动云就会向正左上方相对运动。

这个时候我们发现，答案只会有1或者2，因为初始时都不会相交，而一旦移动之后，有相交的部分，其他的云都不会在这块。

然后既然只有一种运动方式，我们发现这条路径是 y = -x + b，是否会相遇，取决于映射的 b，可以理解为将平面以一个 \frac{\pi}{2} 倾斜角切开。

注意数据较大，需要离散化。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
int T;
inline int read() {
  char ch = getchar(); int p = 1, x = 0;
  while(!isdigit(ch)) {if(ch == '-') p = -1; ch = getchar();}
  while(isdigit(ch)) {x = x * 10 + ch - '0';}
  return x;
}
int n;
const int N = 1e6 + 10;
struct Num{int val, pos;};
int x, y, w, h, d[N], l[N], r[N];
ll s[N << 1];
vector<int> p;
/*
相对运动一时刻就是向右移动的不动，向上移动的向左上动
*/
int main()
{
  // freopen(".in", "r", stdin);
  // freopen(".out", "w", stdout);
  scanf("%d", &T);
  while(T--) {
    scanf("%d", &n);
    p.clear();
    for(int i = 1; i <= n; i++) {
      /*
      如果不进行离散化，
      */
      // x = read(), y = read(), w = read(), h = read(), d[i] = read();
      scanf("%d%d%d%d%d", &x, &y, &w, &h, &d[i]);
      l[i] = x + y;
      r[i] = x + y + w + h - 1;
      p.emplace_back(l[i]);
      p.emplace_back(r[i]);
    }
    memset(s, 0, sizeof(s));
    sort(p.begin(), p.end());
    auto q = unique(p.begin(), p.end());
    for(int i = 1; i <= n; i++) {
      l[i] = lower_bound(p.begin(), q, l[i]) - p.begin() + 1;
      r[i] = lower_bound(p.begin(), q, r[i]) - p.begin() + 1;
      if(d[i] == 0) {
        s[l[i]]++;
        s[r[i] + 1]--;
      }
    }
    for(int i = 1; i <= n * 2 + 1; i++) s[i] += s[i - 1];
    for(int i = 1; i <= n * 2 + 1; i++) s[i] += s[i - 1];
    int ans = 1;
    for(int i = 1; i <= n; i++) {
      if(d[i] == 1) {
        if(s[r[i]] > s[l[i] - 1]){
          ans = 2;
          break;}
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}