Закрасить линию

Процессор чтоль какой древний? 10000 * 10000 = 100 000 000 пар операций (сравнить/перейти к следующему) - это меньше секунды.

 

и что теперь? все алгоритмы писать через ж-у? а если будет миллион кусков? я априори не знаю сколько там их будет.

 

В общем получается что-то типа этого:

Код (Text):

1. #include <set>
2.  
3. typedef unsigned int    uint_t;
4. typedef signed int      int_t;
5. typedef unsigned __int8 uint8_t;
6. typedef signed __int8   int8_t;
7.  
8. struct block_t
9. {
10.     mutable size_t start;
11.     mutable size_t end;
12.  
13.     inline block_t(size_t start, size_t end) :
14.         start(start),
15.         end(end)
16.     {
17.     }
18.  
19.     inline bool operator < (block_t const& val) const
20.     {
21.         return end < val.start;
22.     }
23.  
24.     inline bool operator == (block_t const& val) const
25.     {
26.         return start <= val.end && end >= val.start;
27.     }
28. };
29.  
30. class blocks_t :
31.     private std::set<block_t>
32. {
33. private:
34.     typedef std::set<block_t>   inherited;
35.  
36. private:
37.     void union_left_neighbors(iterator i, block_t& block)
38.     {
39.         if ((*i).start <= block.start)
40.         {
41.             block.start = (*i).start;
42.         }
43.         else
44.         {
45.             iterator prev = i;
46.  
47.             while (1)
48.             {
49.                 -- prev;
50.  
51.                 if (prev == inherited::end())
52.                     break;
53.  
54.                 if (*prev < block)
55.                     break;
56.  
57.                 if ((*prev).start <= block.start)
58.                 {
59.                     block.start = (*prev).start;
60.                     inherited::erase(prev);
61.                     break;
62.                 }
63.  
64.                 prev = inherited::erase(prev);
65.             }
66.         }
67.     }
68.  
69.     void union_right_neighbors(iterator i, block_t& block)
70.     {
71.         if (block.end <= (*i).end)
72.         {
73.             block.end = (*i).end;
74.         }
75.         else
76.         {
77.             iterator next = i;
78.             ++ next;
79.  
80.             while (1)
81.             {
82.                 if (next == inherited::end())
83.                     break;
84.  
85.                 if (block < *next)
86.                     break;
87.  
88.                 if (block.end <= (*next).end)
89.                 {
90.                     block.end = (*next).end;
91.                     inherited::erase(next);
92.                     break;
93.                 }
94.  
95.                 next = inherited::erase(next);
96.             }
97.         }
98.     }
99.  
100. public:
101.     typedef inherited::iterator iterator;
102.  
103. public:
104.     void insert_block(size_t start, size_t size)
105.     {
106.         block_t                     block(start, start + size);
107.         std::pair<iterator, bool>   res = inherited::insert(block);
108.  
109.         if (res.second)
110.             return;
111.  
112.         union_left_neighbors(res.first, block);
113.         union_right_neighbors(res.first, block);
114.  
115.         (*res.first).start = block.start;
116.         (*res.first).end = block.end;
117.     }
118. };
119.  
120. int main()
121. {
122.     blocks_t b;
123.  
124.     b.insert_block(1, 1);
125.     b.insert_block(3, 1);
126.     b.insert_block(5, 1);
127.     b.insert_block(7, 1);
128.     b.insert_block(9, 1);
129.     b.insert_block(11, 1);
130.     b.insert_block(0, 20);
131.     b.insert_block(1, 1);
132.     b.insert_block(3, 1);
133.     b.insert_block(5, 1);
134.     b.insert_block(7, 1);
135.     b.insert_block(9, 1);
136.     b.insert_block(11, 1);
137. }

 

srm
Если Вам не к спеху, могу декомпилировать один файлик, там как раз используется такой алгоритм на примере файлов. Алгоритм практически идентичен тому, что предложил r90 с поправками l_inc.