TOPIC
PROBLEM 1464 - URI Fórum 1.0
This topic was solved and cannot recieve new replies.
-
ldcampos replied 9 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!
-
erribeiro replied 8 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
-
lblanger replied 9 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.
-
mbustamante0 replied 9 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; }
