MAPAS - Mapas do gugo

Este fórum serve para discutir os problemas de todas as seções do SPOJBR.

MAPAS - Mapas do gugo

Mensagempor robertogerson » Ter Set 09, 2008 10:10 pm

Alguém consegue ver algum problema com meu código??

Todos os testes que fiz funcionou. Pensei que poderia tomar TLE. Mas estou tomando W.A.

Código: Selecionar tudo
#include <iostream>
#include <math.h>
#include <algorithm>

#define INF 100000000

#define TRACE(x)

#define _inline(f...) f() __attribute__((always_inline)); f
#define all(v) (v).begin(), (v).end()

const double EPS = 1e-1000;

_inline(int cmp)(double x, double y = 0, double tol = EPS) {
   return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
}
using namespace std;

typedef struct{
        int x1, y1, x2, y2;
        long long int A;
        int id;
}mapa;

mapa mapas[30001];
int main(){
    int n, m, T=1;
    while(cin>>n>>m){
        if(n && m) break;
        for(int i = 0; i < n; i++){
                cin>>mapas[i].id>>mapas[i].x1>>mapas[i].y1>>mapas[i].x2>>mapas[i].y2;
                mapas[i].A = abs((long long int)(mapas[i].x2 - mapas[i].x1)*(long long int)(mapas[i].y2-mapas[i].y1));
        }
        cout<<"Teste "<<T++<<endl;
        for(int i = 0; i < m; i++){
                int x, y;
                cin>>x>>y;
                TRACE(cout<<"x, y = "<<x<<","<<y<<endl;)
                int idMenor = 0;
                long long int menorArea = INF;
                double menorCentro = INF;
                for(int j = 0; j < n; j++){
                        if( x >= mapas[j].x1 && x <= mapas[j].x2 &&
                            y >= mapas[j].y1 && y <= mapas[j].y2)
                        {
                            if(menorArea > mapas[j].A){
                                 menorArea = mapas[j].A;
                                 double xc = (double)(mapas[j].x2 - mapas[j].x1)/2;
                                 double yc = (double)(mapas[j].y2 - mapas[j].y1)/2;
                                 double centro =
                                        sqrt(
                                             pow((double)x-xc, 2)+
                                             pow((double)y-yc, 2)
                                        );
                                 menorCentro = centro;
                                 idMenor = mapas[j].id;
                            }
                            else if(menorArea == mapas[j].A){
                                 double xc = (double)(mapas[j].x2 - mapas[j].x1)/2;
                                 double yc = (double)(mapas[j].y2 - mapas[j].y1)/2;
                                 double centro =
                                        sqrt(
                                             pow((double)x-xc, 2)+
                                             pow((double)y-yc, 2)
                                        );
                                 TRACE(cout<<menorCentro<<" "<<centro<<" "<<j+1<<endl;)
                                 if(cmp(centro, menorCentro) < 0){
                                                centro = menorCentro;
                                                idMenor = mapas[j].id;
                                 }
                                 else if(cmp (centro, menorCentro) == 0){
                                             idMenor = min(mapas[j].id, idMenor);
                                 }
                            }
                        }
                }
                cout<<idMenor<<endl;
        }
        cout<<endl;
    }
    return 0;
}

robertogerson
 
Mensagens: 5
Data de registro: Sex Out 12, 2007 11:50 pm

Mensagempor wanderley » Dom Out 05, 2008 1:18 am

você deve ter tomada WA em caso de teste que vem antes de um que poderia dar TLE. você recebe a primeira resposta diferente de aceito.
Wanderley Guimarães
Avatar de usuário
wanderley
Administrador
 
Mensagens: 73
Data de registro: Qui Ago 30, 2007 9:20 pm
Localização: Universidade de São Paulo

Re: MAPAS - Mapas do gugo

Mensagempor carlosfilho » Ter Jan 27, 2009 11:55 pm

Olá, tenho tentado esse problema há alguns dias e também estou tomando RESPOSTA ERRADA (quando também pensei que receberia TEMPO LIMITE EXCEDIDO). Não há a possibilidade de haver algum caso de teste que não cumpra as restrições do enunciado? Estou dizendo isso pois testei meu código para TODAS as entradas da OBI e as saídas estavam todas corretas, porém continuo a receber RESPOSTA ERRADA.

Ou há algum "peguinha" no problema que eu não percebi? Quem puder ajudar, agradeço bastante, pois já estou nesse problema há algum tempo.

Valew,
Carlos Fernandes.
carlosfilho
 
Mensagens: 17
Data de registro: Ter Jan 27, 2009 11:45 pm

Re: MAPAS - Mapas do gugo

Mensagempor Andre » Qua Jan 28, 2009 12:12 am

A primeira coisa, você viu os limite corretamente?
Você zera suas variáveis?
Imprime "Teste n" corretamente?
[]'s
Andre
Andre
 
Mensagens: 834
Data de registro: Sáb Set 01, 2007 11:05 am

Re: MAPAS - Mapas do gugo

Mensagempor carlosfilho » Qua Jan 28, 2009 3:13 pm

Bem, não estou em casa agora mas assim que chegar lá verificarei. Obrigado! =)
carlosfilho
 
Mensagens: 17
Data de registro: Ter Jan 27, 2009 11:45 pm

Re: MAPAS - Mapas do gugo

Mensagempor carlosfilho » Qui Jan 29, 2009 12:29 am

Andre escreveu:A primeira coisa, você viu os limite corretamente?
Você zera suas variáveis?
Imprime "Teste n" corretamente?


A resposta pra todas as suas perguntas é SIM. =/

Será que ninguém passou pelo mesmo problema que eu? Hehe, é muito ruim ficar preso em um problema! =P
carlosfilho
 
Mensagens: 17
Data de registro: Ter Jan 27, 2009 11:45 pm

Re: MAPAS - Mapas do gugo

Mensagempor Andre » Qui Jan 29, 2009 11:19 am

Talvez seja alguma das condiçoes de desempate
[]'s
Andre
Andre
 
Mensagens: 834
Data de registro: Sáb Set 01, 2007 11:05 am

Re: MAPAS - Mapas do gugo

Mensagempor damnerd » Dom Set 06, 2009 5:48 pm

Alguém pode me dar uma dica sobre o algoritmo?
Não consigo imaginar uma maneira de não testar todos os mapas para o pior caso.

eu pensei em dividir o plano em 500x500 retângulos (usando as coordenadas x e y distintas), e marcar para cada área quais mapas a cobrem. mas ainda assim, no pior caso, todos os mapas podem cobrir um determinado retângulo e se todos os pontos de consulta estiverem neste retângulo fico com complexidade O(M*R) .

--
[]'s
damnerd.
--
[]'s
damnerd
damnerd
 
Mensagens: 25
Data de registro: Dom Set 06, 2009 5:37 pm

Re: MAPAS - Mapas do gugo

Mensagempor Andre » Dom Set 06, 2009 6:23 pm

damnerd escreveu:Alguém pode me dar uma dica sobre o algoritmo?
Não consigo imaginar uma maneira de não testar todos os mapas para o pior caso.

eu pensei em dividir o plano em 500x500 retângulos (usando as coordenadas x e y distintas), e marcar para cada área quais mapas a cobrem. mas ainda assim, no pior caso, todos os mapas podem cobrir um determinado retângulo e se todos os pontos de consulta estiverem neste retângulo fico com complexidade O(M*R) .

--
[]'s
damnerd.


A solução é realmente linear para o pior caso em uma consulta, mas no caso médio ela é bem mais rápida do que isso.
[]'s
Andre
Andre
 
Mensagens: 834
Data de registro: Sáb Set 01, 2007 11:05 am

Re: MAPAS - Mapas do gugo

Mensagempor damnerd » Seg Set 07, 2009 7:14 am

A solução é realmente linear para o pior caso em uma consulta, mas no caso médio ela é bem mais rápida do que isso.


Ainda não consegui fazer meu programa rodar abaixo do tempo limite. estou utilizando uma BIT (ou algo parecido) para atualizar a matriz com as regiões retangulares. (para cada mapa, marcar 'todos' os retângulos no intervalo; toma O(n*log(n)) por mapa.) mas, continuo recebendo TLE. qual o detalhe que deixei escapar?
--
[]'s
damnerd
damnerd
 
Mensagens: 25
Data de registro: Dom Set 06, 2009 5:37 pm

Re: MAPAS - Mapas do gugo

Mensagempor Andre » Seg Set 07, 2009 12:31 pm

damnerd escreveu:Ainda não consegui fazer meu programa rodar abaixo do tempo limite. estou utilizando uma BIT (ou algo parecido) para atualizar a matriz com as regiões retangulares. (para cada mapa, marcar 'todos' os retângulos no intervalo; toma O(n*log(n)) por mapa.) mas, continuo recebendo TLE. qual o detalhe que deixei escapar?


Bom, eu não usei uma BIT, só fiz uma ordenação de forma conveniente, você usou o fato de que existem no máximo 500 X e Y diferentes?
[]'s
Andre
Andre
 
Mensagens: 834
Data de registro: Sáb Set 01, 2007 11:05 am

Re: MAPAS - Mapas do gugo

Mensagempor damnerd » Seg Set 07, 2009 1:53 pm

meu algoritmo em pseudo-código:
Código: Selecionar tudo
lista<int> bit[][];
conjunto<int> xdistintos;
conjunto<int> ydistintos;
mapa vet[];

para_cada mapa m em stdin
{
   insere(m, vet)
   insere(m.x1, xdistintos)
   //repete para as outras coordenadas.
}
para_cada mapa m em vet
{
   insere(bit, xdistintos.indice(m.x1), /*outras coordenadas */, m.indice);
}
para_cada ponto p em stdin
{
   mapa resp=0;
   para_cada mapa m em busca(bit, xdistintos.indice(p.x), ydistintos.indice(p.y))
       se m<resp
           resp=m
   imprime m.indice
}

nomeando as variáveis: X (número de coordenadas distintas); N (número de mapas); R (número de consultas)
inserir em xdistintos ou ydistintos toma log(X) {garantido pela STL}, então o primeiro laço custa Nlog(X) = 30.000*log(500) = 300.000
inserir em uma BIT de duas dimensões custa Xlog(X), o segundo laço custa N*Xlog(X) = 30.000 * 500 * log(500) = 150.000.000 //caro!
buscar na BIT de duas dimensões custa log(X), e a lista pode conter todos os mapas, então no pior caso: R*(log(X)+N) = R*N = 1.500.000.000

não consigo pensar em mais nada para otimizar o algoritmo.
--
[]'s
damnerd
damnerd
 
Mensagens: 25
Data de registro: Dom Set 06, 2009 5:37 pm

Re: MAPAS - Mapas do gugo

Mensagempor gogo40 » Seg Set 07, 2009 2:09 pm

Eu usei uma heap multi-dimensional de 4 dimensões ^^. Cada mapa é inserido da seguinte forma
Código: Selecionar tudo
map<int,map<int,map<int, map<int, Mapa> > > > heap;

if(heap[Y_MAX][Y_MIN][X_MAX][X_MIN].id ==NULL || Mapa.id < heap[Y_MAX][Y_MIN][X_MAX][X_MIN].id)
              heap[Y_MAX][Y_MIN][X_MAX][X_MIN]=Mapa;



Ai na hora de pesquisar, dê uma olhada em lower_bound....
Pense um pouco nessa estrutura, pode ser útil. Para não te atrapalhar não digo mais nada...
Avatar de usuário
gogo40
 
Mensagens: 344
Data de registro: Qua Nov 05, 2008 9:35 pm

Re: MAPAS - Mapas do gugo

Mensagempor damnerd » Seg Set 07, 2009 3:52 pm

acabei de conseguir acertar.
otimizei minha BIT para que tanto a inserção de novos mapas quanto a busca por um dado ponto sejam feitos em log^2(X).

obrigado pelas dicas.
--
[]'s
damnerd
damnerd
 
Mensagens: 25
Data de registro: Dom Set 06, 2009 5:37 pm

Re: MAPAS - Mapas do gugo

Mensagempor Andre » Seg Set 07, 2009 9:38 pm

Bom, eu não usei nenhum tipo de estrutura de dados pronta ou não, só usei listas.
[]'s
Andre
Andre
 
Mensagens: 834
Data de registro: Sáb Set 01, 2007 11:05 am

Próximo

Retornar para Arquivo de Problemas

Quem está online

Usuários vendo este fórum: Nenhum usuário registrado online e 0 visitantes

cron