P2950 [USACO09OPEN] Bovine Embroidery G

Bessie has taken up the detailed art of bovine embroidery. Cows embroider a cloth mounted in a circular hoop of integer radius $d$ ($1 \le d \le 50000$). They sew $N$ ($2 \le N \le 50000$) straight threads, each from one point on the edge of the hoop to another point on the edge (no two embroidered points share a location on the hoop's edge). Being mathematically inclined, Bessie knows a formula of the form $ax + by + c = 0$ for each straight thread. Conveniently, $a$, $b$, and $c$ are integers ($-1000000 \le a \le 1000000$, $-1000000 \le b \le 1000000$, $-1000000 \le c \le 1000000$). Even more conveniently, no two threads coincide exactly. At least one of $a$ and $b$ is non-zero for each thread’s formula. Perhaps less conveniently, Bessie knows that her set of formula coefficients also includes some lines that do not pass through the interior of the hoop’s circle. The origin $(0, 0)$ is at the exact center of the hoop, so all points on the hoop’s edge are at distance $d$ from the origin. Bovine embroidery is more highly regarded when the number of thread intersections is maximized. Help Bessie count the number of pairs of threads that intersect on the cloth, i.e., whose intersection point lies within distance $d$ of the origin. If $k$ threads meet at the same point inside the circle, they contribute $\binom{k}{2}$ pairs (e.g., three threads give three pairs; four threads give six pairs).

- Line 1: Two space-separated integers $N$ and $d$. - Lines 2 to $N+1$: Line $i+1$ describes thread $i$ with three integers: $a$, $b$, and $c$.

- Line 1: One integer, the count of pairs of threads that intersect inside the circle of radius $d$.

The two lines are $x = 0$ and $y = 0$. The two lines intersect at $(0, 0)$, which is clearly within distance $1$ of the origin. Translated by ChatGPT 5