Nigdy nie mów nigdy (omówienie)

02.02.2011

Pomimo treści nasuwającej skojarzenia z analizą matematyczną, postawiony w zadaniu problem był natury geometrycznej. W istocie bowiem zadanie można sformułować tak:

  • Mając dany zbiór odcinków na płaszczyźnie sprawdź, czy istnieje w nim para odcinków o niepustym przecięciu.

Przy czym odcinki było podane w specyficznej postaci, jako spójny fragment wykresu funkcji liniowej o współczynnikach całkowitych. 

Niektórzy Zawodnicy decydowali się na konwersję tej postaci do ogólnej postaci odcinka jako pary punktów rzeczywistych. To ryzykowne podejście, gdyż obliczenia na liczbach zmiennopozycyjnych obarczone są błędem wynikającym z niedokładnej reprezentacji liczb rzeczywistych w pamięci komputera. Zadanie dało się rozwiązać operując cały czas na postaci wejściowej, przy użyciu wyłącznie liczb całkowitych.

Rozwiązanie wzorcowe oparte było na technice zwanej "zamiataniem". Wyobraźmy sobie pionową linię ("miotłę"), przesuwającą się przez płaszczyznę z lewej strony na prawą. Jeśli w jakiś sposób uda nam się reprezentować w pamięci komputera "listę" odcinków aktualnie przecinających miotłę uporządkowanych w kolejności od dołu do góry ( wg punktu przecięcia z miotłą ), to będziemy w stanie łatwo wykryć przecięcie odcinków. 

Wynika to z następujących obserwacji:

  • Przeciąć mogą się tylko te odcinki, które w momencie przecięcia są sąsiednie na "miotle" ( na liście wierzchołków przecinających prostą )
  • Dopóki nie nastąpi przecięcie ( a wtedy nasz algorytm i tak kończy pracę z wynikiem TAK ), odcinki na miotle nie zmieniają kolejności - jedynie pojawiają się nowe, a stare są usuwane.

W takim razie wystarczy aktualizować stan miotły w tych punktach na osi x (w kolejnośc od lewej do prawej), w której musimy dodać do niej nowy odcinek albo usunąć stary, każdorazowo sprawdzając czy nowo utworzeni sąsiedzi ( nowo dodany wierzchołek z sąsiadami w przypadku dodawania, dwa odcinki które właśnie przestają być rozdzielane środkowym w przypadku usuwania ) się przecinają. 

Do reprezentacji miotły w pamięci komputera można użyć drzewa zrównoważonego dostępnego w C++ w strukturze set, otrzymamy w ten sposób rozwiązanie o złożoności O(nlogn).

Implementację wzorcową uważamy za na tyle pouczającą, że publikujemy ją (niemal) w całości. W rozwiązaniu struktura Worker przechowuje dane o jednym odcinku w formacie wejściowym, a struktura Intersector poprzez metodę Test umożliwia sprawdzenie, czy dany wektor odcinków zawiera przecinającą się parę, czy nie.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
struct Worker
{
        int s, e, a, b;
        Worker( int s, int e, int a, int b ) : s(s), e(e), a(a), b(b) {}
};
 
bool workersIntersect
(
        const Worker& x,
        const Worker& y
)
{
        if ( x.a == y.a ){
                if ( x.b != y.b ) return false; // parallel, distant
                else return x.s <= y.e && y.s <= x.e;
        }
        else{
                int q = ((x.a-y.a < 0) ? -1 : 1);
                return  ((ll)x.s)*(x.a-y.a)*q <= (y.b-x.b)*q &&
                                        ((ll)x.e)*(x.a-y.a)*q >= (y.b-x.b)*q &&
                                        ((ll)y.s)*(x.a-y.a)*q <= (y.b-x.b)*q &&
                                        ((ll)y.e)*(x.a-y.a)*q >= (y.b-x.b)*q;
        }
}
ll yAt(const Worker& s, int t ){
        assert( s.s <= t && t <= s.e );
        return ((ll)s.a)*t + s.b;
}
 
int t;
 
struct Intersector{
        struct sweepCmp
        {
                bool operator()(const Worker& s1, const Worker& s2) const
                {
                        return yAt(s1, t) < yAt(s2, t); 
                }
        };
 
        enum EventType { START, END}; 
 
        struct Event{
                EventType kind;
                Worker w;
                Event(EventType kind, Worker w) : kind(kind), w(w) {}
                bool operator< ( const Event& rhs ) const
                {
                        if ( kind != rhs.kind ){
                                return kind == END; 
                        }
                        else return false;
                }
        };
 
        bool Test( vector<Worker> v ){
                const int s = (int)v.size();
 
                priority_queue<pair<int, Event> > events;
                for ( int i=  0; i < s; i++){
                        events.push(make_pair(-v[i].s, Event(START, v[i])));
                        events.push(make_pair(-v[i].e, Event(END, v[i])));
                }
 
                set<Worker, sweepCmp> sweep;
 
                while(!events.empty()){
                        t = -events.top().first;
                        Worker s = events.top().second.w;
                        if ( events.top().second.kind == START ){
                                if ( sweep.find(s) != sweep.end() ) return true;
                                sweep.insert(s);
                                set<Worker, sweepCmp>::iterator it = sweep.find(s);
                                assert(it != sweep.end());
                                if ( it != sweep.begin()){
                                        it--;
                                        if ( workersIntersect(s, *it) ) return true;
                                        it++;
                                }
                                it++;
                                if ( it != sweep.begin() ){
                                        if ( workersIntersect(s, *it) ) return true;
                                }
                        }
                        else{
                                set<Worker, sweepCmp>::iterator it = sweep.find(s);
                                assert( it != sweep.end() );
 
                                set<Worker, sweepCmp>::iterator up = it;
                                up++;
                                if ( up != sweep.end() && it != sweep.begin() ){
                                        it--;
                                        if ( workersIntersect(*up,*it) ) return true;
                                }
                                sweep.erase(s);         
                        }
                        events.pop();
                }
                return false;
        }
}

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com