Struts and Springs (UVa Live Archive World Finals Stockholm 2009)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=43&page=show_problem&problem=2454

問題

ウィンドウがn+1個ある。一つ外側のウィンドウがリサイズされると、内側にあるウィンドウは幅やウィンドウとの距離を一部一定に保ちながら移動・リサイズされる。いちばん外側のウィンドウをm回リサイズするので、リサイズ後のウィンドウの位置と大きさを答えよ。
1<=n<=100
1<=m<=100
幅、高さ<=1,000,000

解法

入れ子構造を作って、順にやるだけ。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct Window {
  int pos[2];
  int size[2][3];
  int spring[2][3];
  Window() {;}
  Window(int x, int y, int w, int h, int ls, int xs, int rs, int ts, int ys, int bs) {
    MEMSET(size, 0);
    pos[0] = x; pos[1] = y;
    size[0][1] = w;
    size[1][1] = h;
    spring[0][0] = ls;
    spring[0][1] = xs;
    spring[0][2] = rs;
    spring[1][0] = ts;
    spring[1][1] = ys;
    spring[1][2] = bs;
  }
};


int parent[1000];
int order[1000];
set<int> child[1000];
int n, m, fw, fh;

vector<Window> Resize(const vector<Window> &pWindows, int tw, int th) {
  vector<Window> nWindows = pWindows;
  nWindows[0].size[0][1] = tw;
  nWindows[0].size[1][1] = th;
  REP(iter, 2) {
    REP(j, n) {
      int ci = order[j];
      int pi = parent[ci];
      const Window &ppw = pWindows[pi];
      const Window &pcw = pWindows[ci];
      const Window &npw = nWindows[pi];
      Window &ncw = nWindows[ci];
      int fsize = ppw.size[iter][1];
      int tsize = npw.size[iter][1];
      REP(i, 3) {
        if (!ncw.spring[iter][i]) {
          fsize -= pcw.size[iter][i];
          tsize -= pcw.size[iter][i];
        }
      }
      REP(i, 3) {
        if (ncw.spring[iter][i]) {
          if (pcw.size[iter][i] != 0) {
            double ratio = (double)pcw.size[iter][i] / fsize;
            ncw.size[iter][i] = ratio * tsize + 0.5;
          }
        }
      }
      ncw.pos[iter] = npw.pos[iter] + ncw.size[iter][0];
    }
  }
  return nWindows;
}

bool In(const Window &out, const Window &in) {
  int l1 = out.pos[0];
  int r1 = out.pos[0] + out.size[0][1];
  int t1 = out.pos[1];
  int b1 = out.pos[1] + out.size[1][1];
  int l2 = in.pos[0];
  int r2 = in.pos[0] + in.size[0][1];
  int t2 = in.pos[1];
  int b2 = in.pos[1] + in.size[1][1];
  return l1 <= l2 && r2 <= r1 && t1 <= t2 && b2 <= b1;
}

void dfs(int from, int &cnt) {
  order[cnt++] = from;
  FORIT(it, child[from]) {
    dfs(*it, cnt);
  }
}
void CalcChild(vector<Window> &windows) {
  int n = windows.size();
  REP(i, n) REP(j, n) {
    if (i == j) { continue; }
    if (In(windows[j], windows[i])) {
      if (parent[i] == -1 || In(windows[parent[i]], windows[j])) {
        parent[i] = j;
      }
    }
  }
  REP(i, n) {
    if (parent[i] == -1) { continue; }
    child[parent[i]].insert(i);
  }
  REP(i, n) {
    if (parent[i] == -1) { continue; }
    Window &p = windows[parent[i]];
    Window &c = windows[i];
    REP(iter, 2) {
      c.size[iter][0] = c.pos[iter] - p.pos[iter];
      c.size[iter][2] = p.pos[iter] + p.size[iter][1] - c.pos[iter] - c.size[iter][1];
    }
  }
  int cnt = 0;
  MEMSET(order, 0x0f);
  dfs(0, cnt);
  rotate(order, order + 1, order + n);
}

int main() {
  int test_case = 0;
  while (scanf("%d %d %d %d", &n, &m, &fw, &fh), n|m|fw|fh) {
    test_case++;
    MEMSET(parent, -1);
    REP(i, 1000) { child[i].clear(); }
    vector<Window> windows;
    windows.push_back(Window(0, 0, fw, fh, 0, 1, 0, 0, 1, 0));
    REP(i, n) {
      int x, y, w, h;
      int ls, xs, rs, ts, ys, bs;
      scanf("%d %d %d %d %d %d %d %d %d %d",
          &x, &y, &w, &h, &xs, &ys, &ts, &bs, &ls, &rs);
      if ((ls|xs|rs) == 0) { rs = 1; }
      if ((ts|ys|bs) == 0) { ts = 1; }
      windows.push_back(Window(x, y, w, h, ls, xs, rs, ts, ys, bs));
    }
    CalcChild(windows);
    REP(i, m) {
      int tw, th;
      scanf("%d %d", &tw, &th);
      windows = Resize(windows, tw, th);
      printf("Case %d, resize operation %d:\n", test_case, i + 1);
      FOR(i, 1, windows.size()) {
        const Window &w = windows[i];
        printf("    Window %d, x = %d, y = %d, width = %d, height = %d\n", i, w.pos[0], w.pos[1], w.size[0][1], w.size[1][1]);
      }
    }
  }
}