I am new in geometry.I am trying to solve some basic problem about geometry.Hence i found a nice problem http://lightoj.com/volume_showproblem.php?problem=1058 . But I have no idea about this types of problem. If anyone can help with some idea by how i solve this problem, i will be so much benefited. Please help me. Thanks in advance. :)
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 10.11.2026 07:30:15 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
This problem is about counting equal vectors. If you code in C++ you can use the map container to count them.
I understand your idea Anuar a little bit.Will you explain it ? I am code in c++.
I will try to explain it. First you should compute the equation of each line. In my opinion you should have two map containers map1 and map2. In the first one you should store the A and B coefficients and the second one — A, B anc C. Then just loop over the equations and add map1(A,B)-map2(A,B,C) to the answer. The total complexity is O(N^2 * log(N^2)).
After 40 minutes, 10 submissions and lots of frustration later, I finally got AC on a problem I underestimated. The solution I coded at first got MLE, then TLE after optimisations. I'm not so sure your solution with two maps will suffice, as my initial solution with one map already got MLE. Not only did I have to use unordered_map to save memory and time, but I also had to use the fact that there are no 4 collinear points (so it is sufficient to subtract any occurences of three points equidistant and collinear which can be done using an unordered_set.)
TL;DR — definitely underestimated how challenging time/memory limit could make it.
This problem is also on Codeforces. Link: http://codeforces.me/contest/660/problem/D