Problem 1031 : Simple GUI Application

Problem C: Simple GUI Application
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1031

• 問題概要

パネルが階層的に配置されてる。
上の階層のパネルはその下の階層のパネルに内包されている。
同じ階層にいるパネルは重ならない。
パネルの左上右上の座標が与えられる。
n個の座標が与えられる。
その座標にあるパネルで１番上の階層のパネルの名前と、そのパネルに直接のっているパネルの枚数を答えよ。

• 解法

構文解析？

パーザー書かないとダメかなーと思ってたけど、
記号を空白文字に置き換えて、string stream で読み込んで、スタックで今どのパネルの上か記憶して、
直接のっているパネルの枚数を数えた。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

class GUI{
public:
  int x1, y1, x2, y2;
  int rank, cnt;
  string s;
  GUI(){
    cnt = 0;
  }
  bool operator < (const GUI g) const {
    return rank > g.rank;
  }
  bool on(int x, int y){
    if(s == "OUT OF MAIN PANEL")return true;
    return ( x >= x1 && y >= y1 && x <= x2 && y <= y2);
  }
};


main(){
  
  int n;
  while(cin >> n){
    string s;
    cin >> s;
    rep(i, s.length()){
      if(s[i] == '<' || s[i] == '>' || s[i] == ',' || s[i] == '/')s[i] = ' ';
    }
    stringstream sin(s);
    vector<GUI> G;
    map<string, int> index;
    set<string> used;
    int cnt = 0;
    stack<string> p;
    p.push("OUT OF MAIN PANEL");
    GUI base;
    base.s = "OUT OF MAIN PANEL";
    base.rank = -1;
    G.push_back(base);
    while(sin >> s){
      if(used.find(s) != used.end()){
	cnt--;
	p.pop();
	continue;
      }
      used.insert(s);
      G[index[p.top()]].cnt++;
      p.push(s);
      GUI g;
      g.rank = cnt;
      cnt++;
      g.s = s;
      sin >> g.x1 >> g.y1 >> g.x2 >> g.y2;
      index[s] = G.size();
      G.push_back(g);
    }
    sort(ALL(G));
    rep(i, n){
      int x, y;
      cin >> x >> y;
      FOR(it, G){
	if((*it).on(x, y)){
	  cout << (*it).s << ' ' << (*it).cnt <<endl;
	  break;
	}
      }
    }
  }
}