EasyCoding's blog

Need help
By EasyCoding, history, 9 years ago, In English

You're given N (N ≤ 2000) and N points, then you are given Q (Q ≤ 106), the number of queries, and next Q lines consist Ai, Bi, Ci. For each query you should find how many points are on this line, i.e. how many j that Ai * Xj + Bi * Yj + Ci = 0.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Suppose we have only one query. (It can be easily solved in O(N) time, but the following approach can be used to solve the initial problem) Let's sort all points by value A·Xj + B·Yj. This is actually sorting in the direction orthogonal to the line. Then we have to find the number of points with this value equal to  - C. This can be easily done with two binary searches.

We can see that this solution has two indenedent parts: sorting and answering the query with binary searches. The second can be done in time thus obtainig complexity for Q queries. But we cannot sort points Q times.

To avoid sorting we will do radial sweep (I'm not sure if it is widely used term, if you haven't heard about it, please read this blog ). We will maintain points sorted in some direction and rotate this direction. When the current direction orthogonal to any of the query lines we can answer this query using binary searches. We can see that during that rotation we just need to swap neighbouring points sometimes, moreover, we will do it exactly twice for any pair of points. These moments are when these two points are equal prior to our comparator. This happens if the line containing these two points is orthogonal to the current direction. Now we see that we know for sure in what moments we should do something (answer queries or swap points in the current sorting order). The number of such events is O(N2 + Q). We have to sort them before this sweep.

Overall complexity is

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

For every two points there is only one line that passes through them. So for every two points you find the line and increase the value cnt[A, B, C]. Now, for each query you can know the value ans*(ans-1) (number of pairs) from cnt[Ai, Bi, Ci]. You solve the equation ans*(ans-1) = cnt[Ai, Bi, Ci] (binary search?) then you have the answer.

Please correct me if I missed something.

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

    Nice one.

    The main difficulty is to be able to get the same triple (A, B, C) from every pair of points on one line. Will it be enough to guarantee gcd(A, B) = 1 and A > 0? Let's say that we don't care about horizontal and vertical lines so we assume that A, B ≠ 0. I think it's enough but can anybody confirm?

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

      It doesn't look like a big difficulty. You define:

      typedef long double ld; //or "typedef long long ld;", depending on input format
struct Line {
    ld a, b, c;
    bool operator==(Line other){
        return a*other.b==b*other.a &&
               a*other.c==c*other.a &&
               b*other.c==c*other.b;
    }
};

      I'm not sure that unordered_map<Line,int> works correctly with that, but you can also define operator <, and use map<Line,int>.

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

      gcd(A, B, C) = 1 and first non-zero number of these is positive.

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

    You missed that some given lines pass only through 1 point and some through 0, and this method cannot distinguish these two cases.

    → Reply