Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2006-01-22 23:26:45

Dan Mysak
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 7

http://netoi.ho.com.ua - доступны решения задач третьего тура

На сайті http://netoi.ho.com.ua викладено опис вирішень задач третього туру

Поза форумом

 

#2 2006-01-23 13:10:22

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

Мне кажется в сложности алгоритма, решающего Lake, маленькая неточность... O(E^3), алгоритм Дейкстры - максимум O(V^2), а для построения списка смежных вершин - максимум O(E^2)...
Кстати алгоритм проверки на пересечение отрезка с озером можно оптимизировать проверяя перечечение с вписанной и описанной окружностью...


icq - 402174

Поза форумом

 

#3 2006-01-23 14:06:29

Rybak
Олімпієць
Звідки: Киев, Украина
Зареєстрований: 2005-10-04
Повідомлень: 83
Вебсайт

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

А у меня сложность O(E^2), а точнее O(L^2 * V^2 + L^3), где L - количество озер (<=10), V - максимальное количество вершин в озере (<= 20). В приниципе можно было бы и за O(L^2 * V log V + L^3), и наверное даже за O(L^2 * log V + L^3), но уже слишком громоздко бы вышло.

Все тесты работают не дольше 0.04 сек

Поза форумом

 

#4 2006-01-23 22:32:29

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

2xXx почему это О(Е*Е)?
всего пар вершин Е*Е да еще для каждой пары нужно все ребра перебрать (еше О(Е))


ICQ 233-416-344

Поза форумом

 

#5 2006-01-24 13:42:22

Nicky Nick
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-25
Повідомлень: 48
Вебсайт

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

xXx написав:

Кстати алгоритм проверки на пересечение отрезка с озером можно оптимизировать проверяя перечечение с вписанной и описанной окружностью...

Очень сомневаюсь. Легко придумать пример, для которого это не так: представь себе большой квадрат, угол которого пересекает маленький отрезок. Это пересечение не будет отловлено.

Відредаговано Nicky Nick (2006-01-24 13:44:15)

Поза форумом

 

#6 2006-01-24 13:49:58

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

Ivan написав:

2xXx почему это О(Е*Е)?
всего пар вершин Е*Е да еще для каждой пары нужно все ребра перебрать (еше О(Е))

E - количество рёбер, самый простой алгоритм, это для каждого ребра проверяем пересечение с остальными рёбрами...


icq - 402174

Поза форумом

 

#7 2006-01-24 13:56:52

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

Nicky Nick написав:

xXx написав:

Кстати алгоритм проверки на пересечение отрезка с озером можно оптимизировать проверяя перечечение с вписанной и описанной окружностью...

Очень сомневаюсь. Легко придумать пример, для которого это не так: представь себе большой квадрат, угол которого пересекает маленький отрезок. Это пересечение не будет отловлено.

OK... Тогда можно конкретный пример?
Ладно, уговорил, объясню:
1. Проверяем пересечение с вписанной окружностью
2. Если пересекает, то 100% отрезок пересекает и многоугольник, goto N.
3. Проверяем на пересечение с описанной окружностью
4. Если не пересекает, то 100% отрезок не пересекает многоугольник, goto N.
5. Проверяем на пересечение со сторонами многоугольника...
...
N. ...


icq - 402174

Поза форумом

 

#8 2006-01-24 14:41:12

Rybak
Олімпієць
Звідки: Киев, Украина
Зареєстрований: 2005-10-04
Повідомлень: 83
Вебсайт

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

Пересечение можно проверять за О(1).

Пересекаем с описанной окружностью. Получаем отрезок AB (если получаем одну точку или ничего не получаем - внутренних точек нету; если А или В - центр озера, то общая точка есть (в нашем случае невозможно, т.к. ребра исходят из вершин)).

Посмотрим на то, как задается озеро: количество вершин Е, и координаты одной вершины. Проведем лучи из центра ко всем вершинам - они разделят окружность на Е секторов. Определим за О(1), каким секторам принадлежит точка А - таких секторов будет 2 (если А лежит на луче) либо 1 (в противном случае). Точно так же для вершины В. Очевидно, что если нет сектора, содержащего обе точки, то АВ пересекает озеро (потому что пересекает границу(ы) секторов).

Если же А и В лежат в одном секторе, остается проверить наличие общих внутренних точек у отрезка и треугольника.

П.С. Для определения секторов, которым принадлежат точки, считаем углы и делим нацело.

Відредаговано Rybak (2006-01-24 14:42:50)

Поза форумом

 

#9 2006-01-24 15:54:00

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

Rybak написав:

Пересечение можно проверять за О(1).
...

А вот это всегда правивильно!!! smile

Відредаговано xXx (2006-01-24 15:56:48)


icq - 402174

Поза форумом

 

#10 2006-01-24 20:56:14

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

Объясни пожалуйста про перебор всех пар отрезков


ICQ 233-416-344

Поза форумом

 

#11 2006-01-24 21:12:56

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

Pascal

Код:

For i:=1 to E do
    For j:=1 to E do
        If i<>j Then Begin 
            ...
        End;

C++

Код:

for(i=0;i<E;i++)
    for(j=0;j<E;j++)
        if(i!=j){
            ...
        }

Перебераем все пары вершин (отрезки)...
Для каждого такого отрезка перебераем все пары вершин, проверяем принадлежит ли пара одному многоугольнику, если да то проверяем на пересечение... Так можно добиться E^2...

Відредаговано xXx (2006-01-24 21:14:02)


icq - 402174

Поза форумом

 

#12 2006-01-25 11:57:07

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

Понял. Тоесть. у тебя число отрезков порядка квадрата вершин, да? Просто у меня число отрезков равно числу вершин. (отрезками я считею именн стороны озер)


ICQ 233-416-344

Поза форумом

 

#13 2006-01-25 11:58:58

Rybak
Олімпієць
Звідки: Киев, Украина
Зареєстрований: 2005-10-04
Повідомлень: 83
Вебсайт

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

Стоп. Что-то я запутался.
Что такое Е?

xXx написав:

...
Перебераем все пары вершин (отрезки)...
Для каждого такого отрезка перебераем все пары вершин, проверяем принадлежит ли пара одному многоугольнику, если да то проверяем на пересечение... Так можно добиться E^2...

Сколько у нас вершин? Е?

Если мы перебираем все пары вершин, это уже O(E^2). Плюс пересечь со сторонами многоугольников каждую - итого O(E^3) разве нет?

Вот твой код:

* Проверка пересечения отрезка с озером

Код:

class Polygon{
...
public:
    bool Cross(double x0,double y0,double x1,double y1){
        ...
        for(i=1;i<n;i++)
            if(::CrossLine(x0,y0,x1,y1,p[i].x,p[i].y,p[i-1].x,p[i-1].y))
                return true;
        return false;
    }
}P[10];

* Пересечение отрезка со всеми озерами - O(E)

Код:

...
bool VerifyLine(double x0,double y0,double x1,double y1){
    short i=0;
    for(;i<N;i++)
        if(P[i].Cross(x0,y0,x1,y1))
            return false;
    return true;
}

* Заполнение матрицы смежности

Код:

...

int main(){
        ...
        for(i=0;i<N;i++) 
            for(j=0,LN=VN;j<P[i].n;j++,VN++){ //уже O(E) <<<<<<<<<<<<<<
                p[VN]=&P[i].p[j];
                k=LN+(j+1)%P[i].n;
                AddEdge(VN,k);
                AddEdge(k,VN);
                for(k=0;k<LN;k++) //LN = O(E), поэтому уже O(E^2) <<<<<<<<<<<<<<<<
                    if(VerifyLine(p[VN]->x,p[VN]->y,p[k]->x,p[k]->y)){ //итого O(E^3) <<<<<<
                        AddEdge(VN,k);
                        AddEdge(k,VN);
                    }
            }
}

Відредаговано Rybak (2006-01-25 13:03:12)

Поза форумом

 

#14 2006-01-26 15:51:52

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: http://netoi.ho.com.ua - доступны решения задач третьего тура

Нет, вершин у меня V ( в коде VN )
E - традиционно число рёбер в графе...

E – общее число ребер у всех озер

Відредаговано xXx (2006-01-26 16:03:26)


icq - 402174

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt