Hello, all! I need your help for this problem. Basically, we have n vectors originated in (0, 0) and we are to find a subset of these vectors such that length of their sum is maximum.
Hello, all! I need your help for this problem. Basically, we have n vectors originated in (0, 0) and we are to find a subset of these vectors such that length of their sum is maximum.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | jiangly | 3631 |
| 4 | Kevin114514 | 3574 |
| 5 | maroonrk | 3521 |
| 6 | strapple | 3515 |
| 7 | Radewoosh | 3461 |
| 8 | tourist | 3428 |
| 9 | turmax | 3378 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 161 |
| 2 | adamant | 147 |
| 3 | Um_nik | 145 |
| 4 | Dominater069 | 142 |
| 5 | errorgorn | 140 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Try to think about some optimal solution (and some final point). Which vectors should we use to reach this point?
That makes me think about some kind of dp. For example, if the answer is (x, y) then we need to get $$$(x, y)$$$ or $$$(x - a[1].x, y - a[1].y)$$$ from the vectors 2 to n.
What I'm trying to suggest is that the chosen vectors in the optimal solution have some specific property. Finding this property should later lead to a pretty straightforward solution.