Given N <= 10^5 lines, how to find the leftmost intersection of two lines?
Obs : Lines are in the Cartesian Plane
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.11.2024 03:50:33 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
I believe this should work: Go to the dual space. Now you need to find a line going through two of the points that is closest to vertical. This will be one of the pairs of points that are consecutive in x direction. Sketch of proof: assume that a non-consecutive pair (A,B) of points is better and point C between them, one of the pairs (A,C) or (B,C) will be better.
We probably don't need dual space because the rest of solution is equivalent to taking lines with consecutive slopes, but the proof gets less intuitive then.
Can you explain this part? "Now you need to find a line going through two of the points that is closest to vertical."
If we take equivalence (point a,b) <-> (line y=ax+b) then the leftmost point is equivalent to line with minimal slope. I assumed that there exists a line with a<0 then it looks like that \ and more vertical ones have lower slopes. I forgot that there can be no such line, in that case we have a>=0 and the lowest slope will be the line closest to horizontal. You need to check both conditions.
Could you explain what dual space is, please? I've only found some weird Wikipedia articles for mathematicians :(
In a very general picture, we have two types of objects (not necessarily the same) and we define some kind of equivalence between them such that some desired properties are conserved.
A common one is to pair point a,b with line y=ax+b. Notice that dual(dual(a,b))=a,b. For a picture of a bit different point-line duality relation see here.
We have a useful property that if point p lies on line l then point dual(l) lies on line dual(p). This means that any geometry problem that relies only on points, lines and intersections (e.g. no distances are involved) can be transformed into a dual one, that is possibly easier to solve.
In the current case, we have a set of lines and are interested in their intersections. We transform each line into a point and notice that intersection point of lines k and l transforms into a line passing through dual(k) and dual(l).
Thank you very much. One more question — what happens with lines parallel to OY?
AFAIK, it doesn't happen. You have to rotate or translate the plane usually to be able to use duality, depending on its kind (I knew the one with ax + by + 1 = 0 -> (a, b) where translation is more useful)
Yeah, the Wikipedia picture I linked to contains exactly this one. But in the current case I couldn't find any nice indicator of ax+by=1 with a=min and with y=ax+b it is easier.
Auto comment: topic has been updated by misael (previous revision, new revision, compare).
By the way, if you apply the most standard algorithm of checking whether any two of the lines intersect (the set one described in Cormen's book), you might accidentally find the leftmost intersection. Correct me if I'm wrong, I'm not sure about it.
i think we can do binary search on answer, we need to check if there is any intersection with x ≤ mid , so draw a line x = mid and then see intersection of all given lines with this line , now suppose a line with slope m intersects x = mid at some y , then this intersects with some other given line on the left of x = mid if there is another line which intersects x = mid at some y' > y and has slope m' > m. or has y' < y and m' < m
Can someone confirm if this works?
I think this work. If put all (y, m) in a vector<> and then sort, the only way that doesn't exist intersection to the left of mid is if the m's in this vector are in descending order.
Say line f(x) = ax + b. sort by decreasing order of a (which is f(-inf)), now answer is one of the adjacent lines in that sorted list.
This will be effectively same as ania's algorithm, I think.