G. Archery

Codeforces
IDCF10015G
Time1000ms
Memory256MB
Difficulty
English · Original
Formal · Original
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. In 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. From 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. You 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). For 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. _Note that a target can be hit at any point between its 2 end points (inclusive)._ The 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*). Print 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. ## Input The 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*). ## Output Print 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. [samples]
**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of targets. For 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 $. **Constraints** 1. $ 1 \leq N \leq 100 $ 2. $ -100 \leq x_{i,j}, y_{i,j} \leq 100 $ for all $ i \in \{1, \dots, N\}, j \in \{1,2\} $ 3. For all $ i $, the segment $ T_i $ does not contain the origin. **Objective** Let $ \theta \in [0, 2\pi) $ be a uniformly random shooting direction. For each target $ T_i $, define an indicator variable: $$ I_i(\theta) = \begin{cases} 1 & \text{if the ray from } (0,0) \text{ in direction } \theta \text{ intersects } T_i \\ 0 & \text{otherwise} \end{cases} $$ The expected number of penetrated targets is: $$ \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) $$ Compute this expectation, where $ \theta \sim \text{Uniform}[0, 2\pi) $.
API Response (JSON)
{
  "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 i...",
      "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}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments