Counting Chord Intersections in a Circular Hoop

Bessie the cow has taken up the art of embroidery using threads across a circular cloth. The cloth is mounted in a circular hoop of integer radius d (1 ≤ d ≤ 50,000). Bessie embroideres N (2 ≤ N ≤ 50,000) threads. Each thread is a straight-line chord from one point on the edge of the hoop to another, and no two threads share the same endpoint on the hoop’s edge.

Each thread is given by a line equation in the form \[ a x + b y + c = 0, \] with integer coefficients (a, b, c) satisfying -1,000,000 ≤ a, b, c ≤ 1,000,000 and at least one of a and b is nonzero. Note that no two threads coincide. Unfortunately, some of the given line equations do not actually pass through the interior of the hoop. Since the hoop is a circle centered at the origin (0,0) with all edge points at distance d from the origin, a line will produce a valid embroidered thread (i.e. a chord connecting two distinct points on the edge) if and only if its distance from the origin is strictly less than d. Recall that the distance from the origin to the line \(a x + b y + c = 0\) is \(\displaystyle \frac{|c|}{\sqrt{a^2+b^2}}\).

Bessie values her work by the number of intersecting pairs of threads inside the cloth, that is, the number of pairs whose intersection point lies strictly within the circle (distance from the origin less than d). (Note that if 3 threads intersect at the same point, that counts as 3 intersecting pairs; 4 threads at one intersection count as 6 pairs, and so on.)

Your task is to count the number of pairs of threads that intersect inside the circular cloth.

Hint: For each valid thread (i.e. those for which \(\frac{|c|}{\sqrt{a^2+b^2}} < d\)), the equation together with the circle \(x^2+y^2=d^2\) defines a chord. If you compute the two intersection points with the circle and convert them to angles (in radians, using \(\mathtt{atan2}\)), then each chord can be represented by a pair of angles. After an appropriate rotation of the circle (so that no chord crosses the cut), it turns out that two chords intersect if and only if their endpoints are interwoven (that is, for chords represented by \((a_1,b_1)\) and \((a_2,b_2)\) with \(a_1 < a_2\), they intersect if and only if \(a_1 < a_2 < b_1 < b_2\)). This observation should help you design an \(O(N \log N)\) solution.

inputFormat

The first line contains two integers d and N separated by a space.

Each of the next N lines contains three integers a, b, and c representing the line equation
\(a x + b y + c = 0\).

It is guaranteed that no two threads share an endpoint on the circle, and no two threads coincide.

outputFormat

Output a single integer: the number of pairs of threads that intersect within the circle \(x^2+y^2<d^2\).

sample

2 3
1 0 -1
0 1 -1
1 -1 0

1