SIR_MBSTU's blog

How to solve Light OJ 1058 — Parallelogram Counting ?

By SIR_MBSTU, 9 years ago, In English

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. :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is about counting equal vectors. If you code in C++ you can use the map container to count them.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I understand your idea Anuar a little bit.Will you explain it ? I am code in c++.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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)).

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is also on Codeforces. Link: http://codeforces.com/contest/660/problem/D

→ Reply