{"raw_statement":[{"iden":"statement","content":"Lately the communication between planets has been an important issue, which is why the Earth has made many efforts to be connected to every other planet in the universe.\n\nThe Universal Network Army of Lasers (UNAL) is trying to connect the Earth with other planets in the universe. In order to make this, the UNAL uses a laser machine which each time it is used, it sends a communication signal in the form of a ray of light in the direction of the planet.\n\nThis laser machine is so powerful, that a ray of light generated by it is capable to cross all the planets it touches until the end of the universe. Moreover, when it fires a ray of light in one direction it also fires a ray of light in the opposite direction. \n\nGiven the coordinates of all the planets in the universe, help the UNAL to design the way to communicate the Earth with all other planets in the universe using the machine the minimum number of times.\n\nThe first line of input contains one integer n (1 ≤ n ≤ 5000), the number of planets.\n\nThe next n lines contains the list of coordinates of the planets. In particular, the i - th line contains three integers xi, yi, zi ( - 109 ≤ xi, yi, zi ≤ 109), the coordinates of the i - th planet, respectively. The Earth is the first planet on the list. It is guaranteed that all the planets have different coordinates.\n\nOutput a single integer, the minimun number of times the machine should be used to communicate the Earth with all other planets in the universe\n\n"},{"iden":"input","content":"The first line of input contains one integer n (1 ≤ n ≤ 5000), the number of planets.The next n lines contains the list of coordinates of the planets. In particular, the i - th line contains three integers xi, yi, zi ( - 109 ≤ xi, yi, zi ≤ 109), the coordinates of the i - th planet, respectively. The Earth is the first planet on the list. It is guaranteed that all the planets have different coordinates."},{"iden":"output","content":"Output a single integer, the minimun number of times the machine should be used to communicate the Earth with all other planets in the universe"},{"iden":"examples","content":"Input30 0 01 1 0-1 -1 0Output1Input40 0 01 0 00 1 00 0 1Output3"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of planets.  \nLet $ P = \\{ p_0, p_1, \\dots, p_{n-1} \\} \\subset \\mathbb{Z}^3 $ be the set of planet coordinates, where $ p_0 $ is Earth.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 5000 $  \n2. All $ p_i $ are distinct.  \n3. Each coordinate satisfies $ -10^9 \\leq x_i, y_i, z_i \\leq 10^9 $.  \n\n**Objective**  \nFind the minimum number of laser shots required such that every planet is connected to Earth, where each shot fires a ray in both directions along a line through Earth, and any planet lying on that line is connected.  \n\nEquivalently:  \nLet $ \\mathcal{L} $ be the set of distinct lines passing through $ p_0 $ and at least one other $ p_i $ ($ i \\geq 1 $).  \nEach line corresponds to one laser shot.  \nCompute $ |\\mathcal{L}| $.  \n\nThat is, count the number of distinct directions (unit vectors) from Earth $ p_0 $ to all other planets $ p_i $, where two vectors $ \\vec{v}_i = p_i - p_0 $ and $ \\vec{v}_j = p_j - p_0 $ are considered the same direction if one is a positive scalar multiple of the other (since opposite rays are covered by one shot).  \n\nThus, the objective is:  \n$$\n\\left| \\left\\{ \\text{ray}(\\vec{v}_i) \\,\\middle|\\, i = 1, \\dots, n-1 \\right\\} \\right|\n$$\nwhere $ \\text{ray}(\\vec{v}) $ denotes the equivalence class of vectors under positive scalar multiplication (i.e., direction).","simple_statement":"You are given n planets in 3D space, with Earth as the first planet.  \nEach laser shot from Earth travels in a straight line in both directions and can reach all planets on that line.  \nFind the minimum number of laser shots needed so that Earth can communicate with all other planets.","has_page_source":false}