{"problem":{"name":"G. Archery","description":{"content":"Last summer you were watching all the matches in the 2012 Olympics in London. One of the interesting sports is archery (it's the game of propelling arrows with the use of a bow to hit a target), but i","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10015G"},"statements":[{"statement_type":"Markdown","content":"Last summer you were watching all the matches in the 2012 Olympics in London. One of the interesting sports is archery (it's the game of propelling arrows with the use of a bow to hit a target), but in this problem we are dealing with a new type of archery.\n\nIn this new type of archery, the player has arrows that can penetrate any target and can go to infinity (the same arrow may hit more than one target), and there will be a lot of targets around the player everywhere, and the targets may intersect and/or overlap with each others.\n\nFrom the top view you can model the targets as line segments and the player as a point at the origin (point (0,0) is the origin), also there will be no target which intersects with the player's position.\n\nYou are really interested to calculate the expected number of targets this player can penetrate using one arrow, if he will shoot his arrow in a random direction (there are infinite number of different directions, and each direction has the same probability to be used for the random shoot).\n\nFor example, the following figure explains the first sample test, where the player is at the origin, and there are two targets T1 with end points (1,5) and (3,3), and T2 with end points (3,5) and (6,2), you can notice that there is a region where the player can shoot an arrow and penetrate the two targets, and there are two regions where he can penetrate only one target, and the last region he will not penetrate any target.\n\n_Note that a target can be hit at any point between its 2 end points (inclusive)._\n\nThe input starts with a line containing one integer *N* (1  ≤  *N*  ≤  100) representing the number of targets in the game. Followed by *N* lines, the *ith* line contains 4 integers separated by a single space *X1* *Y1* *X2* *Y2* (-100  ≤  *X1*, *Y1*, *X2*, *Y2*  ≤  100) representing the *ith* target end points (*X1*,*Y1*) and (*X2*,*Y2*).\n\nPrint on a single line, the expected number of targets the player can penetrate using one arrow. The absolute or relative error in the answer should not exceed 10 - 6.\n\n## Input\n\nThe input starts with a line containing one integer *N* (1  ≤  *N*  ≤  100) representing the number of targets in the game. Followed by *N* lines, the *ith* line contains 4 integers separated by a single space *X1* *Y1* *X2* *Y2* (-100  ≤  *X1*, *Y1*, *X2*, *Y2*  ≤  100) representing the *ith* target end points (*X1*,*Y1*) and (*X2*,*Y2*).\n\n## Output\n\nPrint on a single line, the expected number of targets the player can penetrate using one arrow. The absolute or relative error in the answer should not exceed 10 - 6.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of targets.  \nFor each $ i \\in \\{1, \\dots, N\\} $, let $ T_i $ be a line segment with endpoints $ P_{i,1} = (x_{i,1}, y_{i,1}) $ and $ P_{i,2} = (x_{i,2}, y_{i,2}) $, such that the origin $ (0,0) $ does not lie on any $ T_i $.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 100 $  \n2. $ -100 \\leq x_{i,j}, y_{i,j} \\leq 100 $ for all $ i \\in \\{1, \\dots, N\\}, j \\in \\{1,2\\} $  \n3. For all $ i $, the segment $ T_i $ does not contain the origin.\n\n**Objective**  \nLet $ \\theta \\in [0, 2\\pi) $ be a uniformly random shooting direction. For each target $ T_i $, define an indicator variable:  \n$$\nI_i(\\theta) = \n\\begin{cases}\n1 & \\text{if the ray from } (0,0) \\text{ in direction } \\theta \\text{ intersects } T_i \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$  \nThe expected number of penetrated targets is:  \n$$\n\\mathbb{E}\\left[\\sum_{i=1}^N I_i(\\theta)\\right] = \\sum_{i=1}^N \\mathbb{P}\\left( \\text{ray in direction } \\theta \\text{ intersects } T_i \\right)\n$$  \nCompute this expectation, where $ \\theta \\sim \\text{Uniform}[0, 2\\pi) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10015G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}