fork download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. class Ponto {
  8. 	public double x, y;
  9. 	public Ponto(double x, double y) {
  10. 		this.x = x;
  11. 		this.y = y;
  12. 	}
  13. }
  14.  
  15. class Aresta {
  16. 	private Ponto inicio, fim;
  17. 	public Aresta(Ponto i, Ponto f) {
  18. 		inicio = i;
  19. 		fim = f;
  20. 	}
  21. 	public Ponto getInicio() {
  22. 		if (inicio == null)
  23. 			inicio = new Ponto(0,0);
  24. 		return inicio;
  25. 	}
  26. 	public Ponto getFim() {
  27. 		if (fim == null)
  28. 			fim = new Ponto(0,0);
  29. 		return fim;
  30. 	}
  31. 	public void setInicio(Ponto i) {
  32. 		this.inicio = i;
  33. 	}
  34. 	public void setFim(Ponto f) {
  35. 		this.fim = f;
  36. 	}
  37. 	public boolean verificaSePtoInterceptaArestaPelaDireita(Ponto p) {
  38. 		Ponto p1 = getInicio();
  39. 		Ponto p2 = getFim();
  40.  
  41. 		double ymin = Math.min(p1.y, p2.y);
  42. 		double ymax = Math.max(p1.y, p2.y);
  43.  
  44. 		double y = p.y;
  45. 		double x = p1.x + (y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y);
  46.  
  47. 		boolean estaAEsquerda = p.x < x;
  48. 		boolean interceptaSegmento = y >= ymin && y <= ymax;
  49. 		return estaAEsquerda && interceptaSegmento;
  50. 	}
  51. }
  52.  
  53. class Poligono {
  54. 	public List<Aresta> arestas;
  55.  
  56. 	public Poligono(List<Aresta> a) {
  57. 		setArestas(a);
  58. 	}
  59. 	public List<Aresta> getArestas() {
  60. 		if (arestas == null) {
  61. 			arestas = new ArrayList<Aresta>();
  62. 		}
  63. 		return arestas;
  64. 	}
  65. 	public void setArestas(List<Aresta> arestas) {
  66. 		this.arestas = arestas;
  67. 	}
  68.  
  69. 	public boolean isDentroDoPoligono(Ponto p) {
  70. 		int numeroDeArestasInterceptadas = 0;
  71. 		Iterator<Aresta> i = getArestas().iterator();
  72. 		while (i.hasNext()) {
  73. 			if (i.next().verificaSePtoInterceptaArestaPelaDireita(p)) {
  74. 				numeroDeArestasInterceptadas++;
  75. 			}
  76. 		}
  77.  
  78. 		return numeroDeArestasInterceptadas % 2 == 1;
  79. 	}
  80. }
  81.  
  82. class Teste {
  83. 	public static void main(String args[]) {
  84. 		Aresta a1 = new Aresta(new Ponto(0,0), new Ponto(0,1));
  85. 		Aresta a2 = new Aresta(new Ponto(0,1), new Ponto(1,1));
  86. 		Aresta a3 = new Aresta(new Ponto(1,1), new Ponto(1,0));
  87. 		Aresta a4 = new Aresta(new Ponto(1,0), new Ponto(0,0));
  88.  
  89. 		List<Aresta> arestas = new ArrayList<Aresta>();
  90. 		arestas.add(a1);
  91. 		arestas.add(a2);
  92. 		arestas.add(a3);
  93. 		arestas.add(a4);
  94.  
  95. 		Poligono p = new Poligono(arestas);
  96.  
  97. 		int pontosDentro = 0;
  98. 		int totalDePontos = 1000000;
  99.  
  100. 		double ladoQuadrado = 2;
  101. 		for (int i = 0; i < totalDePontos; i++) {
  102. 			Ponto ponto = new Ponto(Math.random()*ladoQuadrado, Math.random()*ladoQuadrado);
  103. 			if (p.isDentroDoPoligono(ponto))
  104. 				pontosDentro++;
  105. 		}
  106. 		double relacaoEntreAreas = (1.0*pontosDentro/totalDePontos);
  107. 		System.out.println("Relação: " + relacaoEntreAreas);
  108. 	}
  109. }
Success #stdin #stdout 0.15s 4386816KB
comments (?)
stdin 
Standard input is empty
stdout 
Relação: 0.250163
https://ideone.com/HabvOC
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!