| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | djm03178 | 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.