A head on one's shoulders#1793
The manufacturer of the renowned shampoo Head on Shoulders is deeply committed to ensuring the quality of its products. To achieve this, the company continually enhances various aspects of its shampoo through ongoing research.
Due to legal restrictions, research cannot be conducted on humans, and the company considers animal testing unethical.
As a solution, the company's scientists have developed a mathematical model of a human for their research purposes.
In this model, a human is composed of a head and shoulders. The head is depicted as a circle centered at the point with a radius of , while the shoulders are represented by an infinite line y = -K, where R < K.
The focus of the research is on hair. In this model, each hair is represented by a segment that begins on the head (strictly on the circle) and ends on the shoulders (strictly on the line). Furthermore, no hair intersects the circle of the head at more than one point.
Currently, scientists are investigating the issue of split hairs. A pair of hairs is considered split if the segments representing these hairs intersect at any point.
Given the mathematical model of a human, determine the number of split pairs of hairs.
The first line contains two integers , (1 \leq R < K \leq 1000).
The second line contains an integer (0 \leq N \leq 100\,000) — the number of hairs in the human model.
The next lines each contain real numbers X_h, Y_h, X_S, Y_S — the coordinates of the start and end of each hair. The first pair of coordinates corresponds to the end on the circle of the head, and the second pair corresponds to the end on the shoulders.
It is guaranteed that no hair intersects the circle of the head at more than one point. Additionally, no two hairs have identical starting and ending points.
Output the number of split pairs of hairs.
Example 1