TEMA

PROBLEM 1464 - URI Fórum 1.0

URI Online Judge preguntado 7 years ago

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • Diego 2.0 respondido 5 years ago

    Pessoal estou recebendo w.a. 20%, alguém pode me ajudar?

    Acc 0.024s

    Nota: passei a considerar os pontos colineares no envoltório e recebi acc.

  • Leandro de Campos respondido 6 years ago

    Pesquise Convex Hull, eu usei o algoritmo de Graham Scan. A ideia do problema é contar quantas vezes vc consegue achar um polígono que possa cercar os pontos, depois vc elimina os pontos que pertence ao perímetro do polígono, e continua fazendo isso até ter menos que 3 pontos.A resposta depende da paridade do número de camadas. Tome cuidado com pontos duplicados e retire não só os pontos do Convex Hull mas tbm os que estiverem no perímetro do polígono. Boa sorte!

  • Erick R. Ribeiro respondido 5 years ago

    import java.awt.Point; import java.util.LinkedList; import java.util.Scanner;

    public class CamadasDeCebola{ public static void main(String args[]){ Scanner scanner = new Scanner(System.in);

        int n =  scanner.nextInt();
        while(n != 0){
            LinkedList<Point> pontos = new LinkedList<Point>();         
            for(int i=0;i<n;i++){
                pontos.add(new Point(scanner.nextInt(), scanner.nextInt()));
            }
    
            QuickHull quickHull = new QuickHull(pontos);
            if(quickHull.execute()%2 == 0 ){
                System.out.println("Do not take this onion to the lab!");
            }else{
                System.out.println("Take this onion to the lab!");
            }
            n =  scanner.nextInt();
        }                                              
    }

    } class QuickHull { private LinkedList entrada; private LinkedList result; private int cascas; public QuickHull(LinkedList points){ this.entrada = points; this.result = new LinkedList<>(); cascas = 0; }

    private int[] furtherLeftAndFurtherRight(LinkedList<Point> points){
        int minPoint = -1, maxPoint = -1;
        int minX = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE;
        for (int i = 0; i < points.size(); i++){
            if (points.get(i).x < minX){
                minX = points.get(i).x;
                minPoint = i;
            }
            if (points.get(i).x > maxX){
                maxX = points.get(i).x;
                maxPoint = i;
            }
        }
    
        int[] resultado = {minPoint, maxPoint}; 
        return resultado;
    }
    public int execute(){               
        if (entrada.size() < 3){
            System.out.println("CASCAS: "+cascas);
            return cascas;
        }
    
        /**
         * No eixo x, pega o ponto mais esquerda e direita.     
         */
        int[] resultado = furtherLeftAndFurtherRight(entrada);
        int minPoint = resultado[0];
        int maxPoint = resultado[1];
    
        Point A = entrada.get(minPoint);
        Point B = entrada.get(maxPoint);
    
        /**
         * Adiciona os dois pontos extremos ao Convex Hull.
         */
        result.add(A); 
        result.add(B);
        /**
         * Remove os dois pontos extremos do conjunto de pontos de entrada. 
         */
        entrada.remove(A);
        entrada.remove(B);
    
        /**
         * Criar dois subconjuntos, um a direita da reta e outra a esquerda.
         */
        LinkedList<Point> leftSet  = new LinkedList<Point>();
        LinkedList<Point> rightSet = new LinkedList<Point>();
    
        for (int i = 0; i < entrada.size(); i++){
            Point p = entrada.get(i);
            if (pointLocation(A, B, p) == -1)
                leftSet.add(p);
            else if (pointLocation(A, B, p) == 1)
                rightSet.add(p);
        }
    
        hullSet(A, B, rightSet);
        hullSet(B, A, leftSet);
    
        this.cascas++;        
        if(entrada.size() > 2){   
            for (Point point : entrada) {
                System.out.println(point);
            }
            System.out.println("");
            System.out.println();
            execute();
        }
        //System.out.println("Cascas: "+cascas);
    
        return cascas;
    }
    
    public void hullSet(Point A, Point B, LinkedList<Point> set){
        int insertPosition = result.indexOf(B);
    
        if (set.size() == 0)
            return;
        if (set.size() == 1){
            Point p = set.get(0);
            set.remove(p);
            result.add(insertPosition, p);         
            entrada.remove(p); // ->            
            return;
        }
        Double furtherDistance = Double.MIN_VALUE;
        int furthestPoint = -1;
        for (int i = 0; i < set.size(); i++){
            Point p = set.get(i);
            //int distance = distance(A, B, p);
            double distance = pointToLineDistance(A, B, p);
            if (distance > furtherDistance){
                furtherDistance = distance;
                furthestPoint = i;
            }
        }
    
        Point P = set.get(furthestPoint);
        set.remove(furthestPoint);        
    
        this.result.add(insertPosition, P);
        entrada.remove(P); // ->
    
        /**
         * Determina quais pontos estão a esquerda de AP
         */
    
        LinkedList<Point> leftSetAP = new LinkedList<Point>();
        for (int i = 0; i < set.size(); i++){
            Point M = set.get(i);
            if (pointLocation(A, P, M) == 1){
                leftSetAP.add(M);
            }
        }
    
        /**
         * Determina quais pontos estão a esquerda de PB
         */
    
        LinkedList<Point> leftSetPB = new LinkedList<Point>();
        for (int i = 0; i < set.size(); i++)
        {
            Point M = set.get(i);
            if (pointLocation(P, B, M) == 1)
            {
                leftSetPB.add(M);
            }
        }
        hullSet(A, P, leftSetAP);
        hullSet(P, B, leftSetPB);            
    
    }    
    
    public double pointToLineDistance(Point A, Point B, Point P){
        double normalLength = Math.sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));
        return Math.abs((P.x-A.x)*(B.y-A.y)-(P.y-A.y)*(B.x-A.x))/normalLength;
    }
    
    public int pointLocation(Point A, Point B, Point P){
        int cp1 = (B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x);        
        if (cp1 > 0) 
            return 1;
        else if (cp1 == 0) 
            return 0;
        else 
            return -1;       
    }

    } Olá, estou recebendo "Wrong answer" entranto não estou conseguindo encontrar o erro, estou utilizando a versão quickHull para resolver a questão e me deparei com a seguinte entrada: 5 1 1 2 2 3 3 4 4 5 5

    Take this onion to the lab! Testei essa entrada no toolkit é esse foi o resultado, contudo esses pontos fazem parte da mesma reta, e pelo que sei eles não deveriam formar um convex Hull, estou com essa dúvida também

  • Leonardo Blanger respondido 6 years ago

    Eu também estou com Wrong Answer 20%. O enunciado não explica muito claramente como tratar pontos colineares em cada camada. Já tentei considerá-los e depois ignorá-los, mas continuo com o mesmo resultado.

  • Marcos Bustamante respondido 6 years ago

    Galera alguem pode me ajudar a encontrar o erro?? to levando 20%wa

    #include <iostream>
    #include <stack>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    using namespace std;
    
    typedef struct{
        int x, y;
    }Ponto;
    Ponto p0;
    
    Ponto nextToTop(stack<Ponto> pilha){
        Ponto x = pilha.top();
        pilha.pop();
        Ponto ret = pilha.top();
        pilha.push(x);
        return ret;
    }
    
    int cross(const Ponto & p, const Ponto & p1, const Ponto & p2){
        return (p2.x - p1.x)*(p1.y - p.y) - (p2.y - p1.y)*(p1.x - p.x);
    }
    
    int dist(const Ponto & p1, const Ponto & p2){
        return sqrt(pow(p2.x - p1.x,2)+pow(p2.y - p1.y,2));
    }
    
    int comparacao(const void * a, const void * b){
        Ponto *p1 = (Ponto *)a;
        Ponto *p2 = (Ponto *)b;
        int value = cross(p0, *p1, *p2);
        if(value == 0)
            return dist(p0, *p1) > dist(p0, *p2)?1:-1;
        return value > 0? 1:-1;
    
    }
    
    int convexHull(Ponto pontos[], int n){
        int cont = 0;
        while(n > 3){
            int index = 0;
            for(int i = 1; i < n; ++i){
                if(pontos[i].y < pontos[index].y)
                    index = i;
                else if(pontos[i].y == pontos[index].y && pontos[i].x < pontos[index].x)
                    index = i;
            }
    
            p0 = pontos[index];
            pontos[index] = pontos[0];
            pontos[0] = p0;
    
            Ponto naoSelecionados[n];
    
            Ponto tiraRepitidos[n];
            qsort(&pontos[1], n-1, sizeof(Ponto), comparacao);
    
            tiraRepitidos[0] = pontos[0];
            int k =0;
            for (int i = 1; i < n; ++i){
                if(pontos[i].x != tiraRepitidos[k].x || pontos[i].y != tiraRepitidos[k].y)
                    tiraRepitidos[++k] = pontos[i];
            }
            n = k+1;
            memcpy(pontos, tiraRepitidos, sizeof(Ponto)*n);
    
            stack<Ponto>pilha;
            pilha.push(pontos[0]);
            pilha.push(pontos[1]);
            pilha.push(pontos[2]);
    
            for(int i = 3, j = 0; i < n; ++i){
                while(cross(nextToTop(pilha), pilha.top(), pontos[i]) > 0){
                    naoSelecionados[j++] = pilha.top();
                    pilha.pop();
                }
                pilha.push(pontos[i]);
            }
    
            while(!pilha.empty()){
                --n;
                pilha.pop();
            }
            ++cont;
            memcpy(pontos, naoSelecionados, sizeof(Ponto)*n);
        }
        if(n == 3)
            ++cont;
    
        return cont;
    }
    
    int main(){
        Ponto pontos[3000], x;
        int n;
        while(scanf("%d", &n) && n > 0){
            for(int i = 0; i < n; ++i){
                scanf("%d %d",&pontos[i].x, &pontos[i].y);
            }
    
            int lears = convexHull(pontos, n);
            if(lears%2 == 0)
                cout << "Do not take this onion to the lab!\n";
            else
                cout << "Take this onion to the lab!\n";
        }
        return 0;
    }
  • William Almeida Suzukayama respondido 7 years ago

    Alguma dica ?