Given N rectangles which may or may not intersect. Report a random point Inside any rectangle. (probability of every point chosen must be equal). How to solve this problem?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 164 |
| 3 | awoo | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 155 |
| 6 | maroonrk | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 28.05.2024 21:07:12 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Points that appear in more that one rectangle have more probability or not?
No, every point should have same probability of being chosen irrespective of numbers of rectangles it appears in.
One more question :)...
Could a rectangle have two or more of these N points in it?
There are N rectangles, you have to report random points inside any of these rectangles. Sorry if I was unclear, See image you need to report any random point from blue region. Image
Partition the rectangle union into area-disjoint rectangles, choose a rectangle randomly accordingly to ratio of its area to sum of areas. Choose random (x,y) coordinate inside.
Looks good to me. Can you tell how can I "Partition the rectangle union into area-disjoint rectangles"? (algorithm)
If coordinates are not big, you can get any random point until you get one which is inside one of the rectangles. That will still give you a uniform distribution although at a time complexity cost.