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

А у меня сложность 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 сек

xXx написав:

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

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

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

Nicky Nick написав:

xXx написав:

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

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

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

Rybak написав:

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

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

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

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)

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

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)