eolymp
bolt
Try our new interface for solving problems
Məsələlər

Bisectors

Bisectors

\includegraphics{https://static.e-olymp.com/content/16/16c4da63a8022069d1ad7836d25cd7f84a829ee3.jpg} We all probably know how to find equation of bisectors in Coordinate Geometry. If the equations of two lines are \textbf{a_ix + b_iy + c_i = 0} and \textbf{a_jx + b_jy + c_\{j \}= 0}, then the equations of the bisectors of the four angles they create are given by . Now one has to be quite intelligent to find out for which angles to choose the '\textbf{+}' (plus) sign and for which angles to choose the '\textbf{-}' (minus) sign. You will have to do similar sort of choosing in this problem. Suppose there is a fixed point (\textbf{C_x}, \textbf{C_y}) and there are \textbf{n} (\textbf{n} ≤ \textbf{10000}) other points around it. No two points from these \textbf{n} points are collinear with (\textbf{C_x}, \textbf{C_y}). If you connect all these point with (\textbf{C_x}, \textbf{C_y}) you will get a star-topology like image made of \textbf{n} lines. The equations of these \textbf{n} lines are also given and only these equations must be used when finding the equation of bisectors. This \textbf{n} lines create \textbf{n(n-1)/2} acute or obtuse angles in total and so they have total \textbf{n(n-1)/2} bisectors. You have to find out how many of these bisectors have equations formed using the \textbf{+} sign. The image below shows an image where \textbf{n = 5}, \textbf{C_\{x \}= 5} and \textbf{C_\{y \}= 2}. This image corresponds to the only sample input. \InputFile The input file contains maximum \textbf{35} sets of inputs. The description of each set is given below: First line of each set contains three integers \textbf{C_x}, \textbf{C_y} (\textbf{-10000} ≤ \textbf{C_x}, \textbf{C_y} ≤ \textbf{10000}) and \textbf{n} (\textbf{0} ≤ \textbf{n} ≤ \textbf{10000}). Each of the next \textbf{n} lines contains two integers \textbf{x_i}, \textbf{y_i} (\textbf{-20000} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{20000}) and a string of the form \textbf{a_ix + b_iy + c_\{i \}= 0}. Here (\textbf{x_i}, \textbf{y_i}) is the coordinate of a point around (\textbf{C_x}, \textbf{C_y}) and the string denotes the equation of the line segment formed by connecting (\textbf{C_x}, \textbf{C_y}) and (\textbf{x_i}, \textbf{y_i}). You can assume that (\textbf{-100000} ≤ \textbf{a_i}, \textbf{b_i} ≤ \textbf{100000}) and (\textbf{-2000000000} ≤ \textbf{c_i} ≤ \textbf{2000000000}). This equation will actually be used to find the equations of bisectors of the angles that this line creates. Input is terminated by a set where the value of \textbf{n} is zero. \OutputFile \includegraphics{https://static.e-olymp.com/content/ff/ff588c74aae218107840e844ebbfb48a4f45e599.jpg} \includegraphics{https://static.e-olymp.com/content/16/16c4da63a8022069d1ad7836d25cd7f84a829ee3.jpg} For each set of input produce one line of output. This line contains an integer number \textbf{P} that denotes of the bisector equations how many are formed using the \textbf{+} sign in the bisector equation .
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
5 2 5 
12 7 10x-14y-22=0 
1 -4 24x-16y-88=0 
4 10 32x+4y-168=0 
-1 9 56x+48y-376=0 
12 -3 -10x-14y+78=0 
10 10 0
Çıxış verilənləri #1
4
Mənbə ACM-ICPC Thailand National Programming Contest 2010, Prince of Songkla University Phuket Campus 24 August 2010