Programação Simples OO

[Gerson]

Escrever um algoritmo que leia 10 pontos no plano 2D (cada ponto contém suas coordenadas X e Y) e informe quais são os dois pontos mais próximos.

existe algum jeito de fazer isso orientado a objetos sem fazer um código gigante e pedrero? nao entendo nada de OO...
valeu

[Bombastic]

sim, depende principalmente da linguagem

qual é a formula da distancia entre 2 pontos e qual linguagem vc tava pensando?

[Ted]

class Ponto
{
public Ponto(int x, int y);
public double distancia(Ponto p);
public double getX();
public double getY();
}

[tdf]

Ah, até tava tentando pensar na fórmula aqui, mas não tenho mais saco pra essas coisas... até pq no google tem pronto, algum nerd já pensou nisso pra você, pode ter certeza ehuahe

[Ted]

Distancia de 2 pontos é raiz da soma dos quadrados das distâncias x e y (Pitágoras)

[Gerson]

sim a formula da distancia entre dois pontos eu sei po é só fazer pitágoras e tal
sqrt( sqr(x1-x2) + sqr(y1-y2) ) ou...em OO
sqrt( sqr(p1.getx( ) - p2.getx( )) + sqr(p1.gety( ) - p2.gety( )) )
só que aí olha quantos pontos sao...vai ficar gigante.
por isso que eu queria saber se n tem um jeito mais simples de fazer em OO
valeu a ajuda ae

[Marcelo]

Dist(a,b) = Raiz( (xa - xb)² + (ya - yb)² )

Eu acho. =)


edit: é, todo mundo postando junto dá nisso. =)

[Ted]

Ou voce faz na força bruta verificando todos os pontos entre si O(n^2), ou então usa subdivisão espacial, como uma quadtree, diminuindo a quantidade de pontos que voce precisa olhar.

[tdf]

Será que se eu pensasse muito assim eu ia chegar no teorema de pitágoras um dia?!
ehauheau

[Gerson]

tdf na 3 serie eu cheguei à conclusão que a soma dos 2 lados de um quadrado é igual a soma dos outros 2 lados do quadrado.
e pois é Ted, não tem jeito mesmo...vai ter que ser na força bruta...fazer o que.
valeu a ajuda ae pessoas

[un4]

vc dá como entrada 10 pontos e quer os 2 mais próximos entre si?

[Ted]

Pra acelerar voce pode nao fazer a raiz, faz so a soma dos quadrados, pois se a soma for menor a raiz tambem é menor.

[Gerson]

de fato ted
isso ae una.
só to com um problema agora e tal.
como que eu vou fazer pra saber de quais pontos que veio a distancia menor e tal.
imaginem um esquema assim
dist = p1.calcula_distancia(p2)
menor = dist
dist = p1.calcula_distancia(p3)
checa_menor(dist,menor)
dist = p1.calcula_distancia(p4)
checa_menor(dist,menor)
....etc
ok, mas como que eu vou saber de quais pontos que veio o menor?

[Sh3lld3r]

eu nao vou fazer sua lição de casa deus uhuhuh

:*

[Biel]

eu tenho que fazer um parecido em java pra semana que vem...
se quiser te envio o programa...

[Gerson]

valeu ae xbiel
acho que isso da talvez...
ufa, me achei

[un4]

Ficou bem simples a minha implementacao aqui...
Fiz uma classe pro ponto e outra classe responsavel por saber quem é maior e guardar esses pontos..

(ruby)

class Ponto
  attr_accessor :x, :y
	
  def initialize(x,y)
    self.x, self.y = x, y
  end
	
  def distancia(p)
    dx = x - p.x
    dy = y - p.y
    # vou usar apenas a soma dos quadrados como o ted falou..
    dx.power!(2) + dy.power!(2)
  end
	
  def to_s
    "(#{x},#{y})"
  end
end

class MaiorDistancia
  attr_accessor :distancia, :p1, :p2
	
  def initialize
    @distancia = 0
  end
	
  def testa(p1, p2)
    d = p1.distancia(p2)
    if d > @distancia
      @p1 = p1
      @p2 = p2	
      @distancia = d
    end
  end

end

p = []
md = MaiorDistancia.new


# Adicionando 3 pontos pra testar
p << Ponto.new(2,2)
p << Ponto.new(4,4)
p << Ponto.new(5,5)

# Loop tosco (ordem n^2), mas que evita o calculo
# entre cada ponto mais de 1x e entre ele mesmo

p[0..(p.length) -2].each do |p1|
  p[1..(p.length) -1 ].each do |p2|
    if p1 != p2
      md.testa(p1,p2)
    end
  end
end

# Wheeeee
puts "Maior distancia entre pontos encontrada:"
puts "#{md.p1} e #{md.p2}: #{Math.sqrt(md.distancia)}"

Maior distancia entre pontos encontrada:
(2,2) e (5,5): 4.24264068711928

eu acho que da pra fazer aquele loop em ruby com 1 linha, mas não to me lembrando como era.. ;(

[Ted]

O loop interno pode ser feito à partir do externo:

for (i = 0; i < n; i++) {
    for (j = i+1: j < n; j++) {
    }
}

Diminui o tempo, mas continua O(n^2)

[Gerson]

valeu ae ted e un4