| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | awoo | 158 |
| 4 | cry | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 152 |
| 9 | maroonrk | 152 |
Last week ACPC 23 was held, and there are problems to upsolve, so let's discuss problems here.
If there is a problem that you can't solve, maybe ask here and someone will help!
I will start with these problems, C. (Cyclic Paths), G. (Golfing Minimally) I couldn't solve them.
here is the problem set.
Link?
There isn't an online mirror for it yet.
Lets call the start point as $$$st$$$ and the hole as $$$h$$$.
Considering each segment $$$s$$$, if the ball should bounce in point $$$p$$$ on $$$s$$$ to fall in the hole then if it bounced before $$$p$$$ it will be below the hole and if it bounced after $$$p$$$ it will be above the hole so you can binary search $$$p$$$.
The binary search is not necessary because you can calculate $$$p$$$ using a formula.
If $$$st$$$ and $$$h$$$ have the same distance from $$$s$$$ then $$$p$$$ will be in the middle of the distance between the projection of $$$st$$$ and $$$h$$$ on $$$s$$$. If $$$st$$$ has smaller distance it will be closer to projection of $$$st$$$. So $$$p$$$ will be the center of mass between $$$st$$$ and $$$h$$$ projection on $$$s$$$.
$$$p = st + dis \times \frac{dis_{st}}{dis_{st} + dis_h}$$$
where $$$dis$$$ is distance between the projection of $$$st$$$ and $$$h$$$ on $$$s$$$. $$$dis_{st}$$$ is the distance of $$$st$$$ from $$$s$$$. $$$dis_h$$$ is the distance from $$$h$$$ to $$$s$$$.
After getting $$$p$$$ then you should check if $$$p$$$ is on $$$s$$$ and the segment from $$$st$$$ to $$$p$$$ doesn't intersect with any other segment so is the segment from $$$h$$$ to $$$p$$$.
The Complexity with binary search is $$$O(n^2 . log_2(10^6 \times precession)$$$ and $$$O(n^2)$$$ without binary search.