icon

2018-11-17

USACO Window Area

链接

想了很久没想出来,不知道怎么把重合的部分去掉。一开始想用容斥原理,但是复杂度不对,最多要$2^{61}$次操作。 偷看了一下答案,要用矩形分割:想象一个矩形从下面浮上来,每次遇到阻碍便分裂成更小的矩形继续上浮。

分成四块,如图:

img

阴影是被遮住的部分,这样分割可以handle所有情况。

#include <bits/stdc++.h>
#ifdef LOCAL
#include <unistd.h>
#endif
using namespace std;
#define rep(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define per(i, b, a) for (int i = (int)b - 1; i >= (int)a; --i)
#define repv(ele, cont) for (auto &ele : cont)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
// END OF TEMPLATE

int height[255], minh = 0, maxh = 0;
int X1[255], Y1[255], X2[255], Y2[255];
const int INVALID = -1;

vector<char> seq;

int siftup(int x1, int y1, int x2, int y2, int h, int i) {
  if (x1 >= x2 || y1 >= y2) return 0;
  if (i == seq.size()) return (x2 - x1) * (y2 - y1);
  if (height[seq[i]] <= h || X1[seq[i]] == INVALID) return siftup(x1, y1, x2, y2, h, i + 1);

  char mask = seq[i];
  int cx1 = max(x1, X1[mask]);
  int cy1 = max(y1, Y1[mask]);
  int cx2 = min(x2, X2[mask]);
  int cy2 = min(y2, Y2[mask]);

  if (cx1 >= cx2 || cy1 >= cy2) return siftup(x1, y1, x2, y2, h, i + 1); // no overlap

  int ret = 0;
  if (cx1 > x1) { ret += siftup(x1, y1, cx1, y2, h, i + 1); }
  if (cx2 < x2) { ret += siftup(cx2, y1, x2, y2, h, i + 1); }
  if (cy1 > y1) { ret += siftup(cx1, y1, cx2, cy1, h, i + 1); }
  if (cy2 < y2) { ret += siftup(cx1, cy2, cx2, y2, h, i + 1); }
  return ret;
}

int main() {
#ifndef LOCAL
  freopen("window.in", "r", stdin);
  freopen("window.out", "w", stdout);
#endif
  memset(X1, INVALID, sizeof X1);
  for (char c = 'a'; c <= 'z'; ++c) seq.eb(c);
  for (char c = '0'; c <= '9'; ++c) seq.eb(c);
  for (char c = 'A'; c <= 'Z'; ++c) seq.eb(c);

  char op, id;
  while (~scanf("%c", &op)) {
    if (op == 'w') {
      int x, y, X, Y;
      scanf("(%c,%d,%d,%d,%d)\n", &id, &x, &y, &X, &Y);
      if (X1[id] != INVALID) continue; // already exist
      X1[id] = min(x, X);
      Y1[id] = min(y, Y);
      X2[id] = max(x, X);
      Y2[id] = max(y, Y);
      height[id] = ++maxh;
    } else if (op == 't') {
      scanf("(%c)\n", &id);
      height[id] = ++maxh;
    } else if (op == 'b') {
      scanf("(%c)\n", &id);
      height[id] = --minh;
    } else if (op == 'd') {
      scanf("(%c)\n", &id);
      X1[id] = INVALID;
    } else if (op == 's') {
      scanf("(%c)\n", &id);
      int area = siftup(X1[id], Y1[id], X2[id], Y2[id], height[id], 0);
      int tot = (X2[id] - X1[id]) * (Y2[id] - Y1[id]);
      printf("%.3f\n", 100.0 * area / tot);
    } else // never happen
      return -1;
  }
  return 0;
}
comments powered by Disqus

search See also