1. Znajduję trójkąt w który trafiłem promieniem.
2. Liczę normalną trójkąta
3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
4. Wyszukuje spośród nich te, które mają wspólny wierzchołek z trójkątem
który trafiłem lub z innym który do niego ma - O(n^2)
5. Wyszukuję tylko te krawędzie trójkątów, które należą tylko do jednego
trójkąta - O(n)

Wiem że da się lepiej. Jakaś podpowiedź? :-)

--
Pozdrawiam,
Mateusz Bogusz

do góry

On 16.02.2017 19:17, Mateusz Bogusz wrote:
> 1. Znajduję trójkąt w który trafiłem promieniem.
> 2. Liczę normalną trójkąta
> 3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
> 4. Wyszukuje spośród nich te, które mają wspólny wierzchołek z trójkątem
> który trafiłem lub z innym który do niego ma - O(n^2)
> 5. Wyszukuję tylko te krawędzie trójkątów, które należą tylko do jednego
> trójkąta - O(n)
>
> Wiem że da się lepiej. Jakaś podpowiedź? :-)

Nie opisałeś problemu, który chcesz roziązać.

pzdr
bartekltg

do góry

On Thu, 16 Feb 2017 19:17:12 +0100, Mateusz Bogusz <m...@o...pl>
wrote:
> 4. Wyszukuje spośród nich te, które mają wspólny wierzchołek z
trójkątem
> który trafiłem lub z innym który do niego ma - O(n^2)

Jeżeli trójkąty znają swoich sąsiadów powinno być szybciej.

do góry

On 16.02.2017 22:52, bartekltg wrote:
> On 16.02.2017 19:17, Mateusz Bogusz wrote:
>> 1. Znajduję trójkąt w który trafiłem promieniem.
>> 2. Liczę normalną trójkąta
>> 3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
>> 4. Wyszukuje spośród nich te, które mają wspólny wierzchołek z trójkątem
>> który trafiłem lub z innym który do niego ma - O(n^2)

A tego w sumie to w ogóle nie rozumiem. Na poziomie gramatycznym.

"..lub z innym który do niego ma"

Co?

>> 5. Wyszukuję tylko te krawędzie trójkątów, które należą tylko do jednego
>> trójkąta - O(n)
>>
>> Wiem że da się lepiej. Jakaś podpowiedź? :-)
>
> Nie opisałeś problemu, który chcesz roziązać.

pzdr
bartekltg

do góry

On Fri, 17 Feb 2017 05:13:29 +0100, bartekltg <b...@g...com>
wrote:
> A tego w sumie to w ogóle nie rozumiem.

Przecież to oczywiste.

do góry

On Thursday, February 16, 2017 at 7:17:16 PM UTC+1, Mateusz Bogusz wrote:
> 1. Znajduję trójkąt w który trafiłem promieniem.
> 2. Liczę normalną trójkąta
> 3. Szukam wszystkich trójkątów, które mają tą samą normalną - O(n)
> 4. Wyszukuje spośród nich te, które mają wspólny wierzchołek z trójkątem
> który trafiłem lub z innym który do niego ma - O(n^2)
> 5. Wyszukuję tylko te krawędzie trójkątów, które należą tylko do jednego
> trójkąta - O(n)
>
> Wiem że da się lepiej. Jakaś podpowiedź? :-)

Struktura danych, która pozwoli ci w czasie stałym dowiedzieć się o sąsiadach.
Np. mógłbyś mieć listę wierzchołków, a trójkąty opisywać indeksami do tej
listy. Natomiast każdy wierzchołek miałby jeszcze listę trójkątów do których
należy. Wtedy stwierdzenie, które trójkąty mają wspólne wierzchołki byłoby
szybkie.

Ad 2. Możesz posortować trójkąty ze względu na normalną, wtedy masz O(nlgn),
albo nawet wrzucić do tablicy mieszającej: O(1) oczekiwany.

w.

do góry

On 17.02.2017 08:51, slawek wrote:
> On Fri, 17 Feb 2017 05:13:29 +0100, bartekltg <b...@g...com> wrote:
>> A tego w sumie to w ogóle nie rozumiem.
>
> Przecież to oczywiste.

No to podziel się.

bartekltg

do góry

On Fri, 17 Feb 2017 14:07:03 +0100, bartekltg <b...@g...com>
wrote:
> No to podziel się.

Bartuś, śmieszny jesteś, grzecznie poprosić nie potrafisz.

do góry

On Fri, 17 Feb 2017 04:10:15 -0800 (PST), Wojciech
Muła<w...@g...com> wrote:
> Ad 2. Możesz posortować trójkąty ze względu na nor=
> malną, wtedy masz O(nlgn),
> albo nawet wrzucić do tablicy mieszającej: O(1) oczekiwany.

Też. Ale struktura która daje łatwy dostęp do sąsiadów pozwala
odłożyć liczenie normalnych (lazy).

do góry

> Struktura danych, która pozwoli ci w czasie stałym dowiedzieć się o
sąsiadach.
> Np. mógłbyś mieć listę wierzchołków, a trójkąty opisywać indeksami do tej
> listy.

To mam, na wejściu dostaję trzy tablice: wierzchołków, trójkątów w
postaci 3 kolejnych indeksów wierzchołków, normalnych wierzchołków.

> Natomiast każdy wierzchołek miałby jeszcze listę trójkątów do których
> należy. Wtedy stwierdzenie, które trójkąty mają wspólne wierzchołki byłoby
> szybkie.

Jakbym to dostawał za free, to tak :-) Większość razy liczę obwiednię
dla nowego zestawu tablic, a cachowanie wszystkiego w pamięci też nie
wchodzi w grę. Ale dzięki za pomysł, pogłówkuję.

> Ad 2. Możesz posortować trójkąty ze względu na normalną, wtedy masz O(nlgn),
> albo nawet wrzucić do tablicy mieszającej: O(1) oczekiwany.

Też zawsze jakiś zysk.

--
Pozdrawiam,
Mateusz Bogusz

do góry