Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //2072 - The Flat Cupboard
- //Live Archive
- /*
- Monte o grafo da seguinte forma: Se um item x precisa ser retirado para um item y sair, então existe uma aresta de x para y.
- Após isso faça uma DFS a partir do item que se deseja tirar contando quantos vértices são atingíveis a partir dele. Todo vértice
- atingível será um elemento que precisa ser retirado antes dele. O número de vértices atingíveis é a resposta.
- */
- #include <cstdio>
- #include <map>
- #include <cstdlib>
- #include <cmath>
- #include <algorithm>
- #include <cstring>
- #include <string>
- #include <vector>
- #define f(i,n) for(int i = 0; i < n; i++)
- using namespace std;
- struct obj{
- int xl, yl, xr, yr;
- int adj[110];
- int last;
- void add(int v){
- adj[last++] = v;
- }
- //Verify if b is above this
- bool above(obj b){
- if(max(xl,b.xl) < min(xr,b.xr)) return yr <= b.yl;
- return false;
- }
- bool operator == (const obj & b) const{
- return xr == b.xr && xl == b.xl && yr == b.yr && yl == b.yl;
- }
- } r[110];
- int n;
- bool read(){
- scanf("%d", &n);
- if(!n) return false;
- f(i,n+1){
- r[i].last = 0;
- scanf("%d%d%d%d", &r[i].xl, &r[i].yl, &r[i].xr, &r[i].yr);
- }
- return true;
- }
- bool mark[110];
- int dfs(int v){
- if(mark[v]) return 0;
- mark[v] = true;
- int res = 1;
- f(i,r[v].last){
- res += dfs(r[v].adj[i]);
- }
- return res;
- }
- void process(){
- memset(mark, false, sizeof(mark));
- f(i,n){
- f(j,n){
- if(i == j) continue;
- if(r[i].above(r[j])) r[i].add(j);
- }
- }
- f(i,n){
- if(r[i] == r[n]){
- printf("%d\n", dfs(i)-1);
- }
- }
- }
- int main(){
- while(read())process();
- return 0;
- }
Add Comment
Please, Sign In to add comment