Skip to content

Commit 185f738

Browse files
committed
fix scanline bug
1 parent 943c110 commit 185f738

1 file changed

Lines changed: 4 additions & 4 deletions

File tree

‎content/russian/cs/decomposition/scanline.md‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ prerequisites:
88
weight: 1
99
---
1010

11-
Метод сканирующей прямой (англ. *scanline*) заключается в сортировке точек или каких-то абстрактных *событий* (англ. *event*) и последующему проходу по ним.
11+
Метод сканирующей прямой (англ. *scanline*) заключается в сортировке точек на координатной прямой либо каких-то абстрактных «событий» по какому-то признаку и последующему проходу по ним.
1212

1313
Он часто используется для решения задач на структуры данных, когда все запросы известны заранее, а также в геометрии для нахождения объединений фигур.
1414

@@ -62,15 +62,15 @@ int scanline(vector<pair<int, int>> segments) {
6262
6363
**Задача.** Дан набор из $n$ отрезков на прямой, заданных координатами начал и концов $[l_i, r_i]$. Требуется найти суммарную длину их объединения.
6464
65-
Как и в прошлой задаче, отсортируем интересные точки и при проходе будем поддерживать число отрезков, покрывающих данную точку. Если оно больше 0, то отрезок который мы прошли с прошлой рассмотренной точки принадлежит объединению, и его длину нужно прибавить к ответу:
65+
Как и в прошлой задаче, отсортируем все интересные точки и при проходе будем поддерживать число отрезков, покрывающих текущую точку. Если оно больше 0, то отрезок, который мы прошли с прошлой рассмотренной точки, принадлежит объединению, и его длину нужно прибавить к ответу:
6666
6767
```cpp
6868
int cnt = 0, res = 0, prev = -inf;
6969
7070
for (event e : events) {
71-
cnt += e.type;
7271
if (prev != -inf && cnt > 0)
73-
res += prev - e.x;
72+
res += e.x - prev; // весь отрезок [prev, e.x] покрыт cnt отрезками
73+
cnt += e.type;
7474
prev = e.x;
7575
}
7676
```

0 commit comments

Comments
 (0)