Incenters

AtCoder

IDagc039_d

Time4000ms

Memory256MB

Difficulty—

Given are $N$ points on the circumference of a circle centered at $(0,0)$ in an $xy$\-plane. The coordinates of the $i$\-th point are $(\cos(\frac{2\pi T_i}{L}),\sin(\frac{2\pi T_i}{L}))$. Three distinct points will be chosen uniformly at random from these $N$ points. Find the expected $x$\- and $y$\-coordinates of the center of the circle inscribed in the triangle formed by the chosen points. ## Constraints * $3 \leq N \leq 3000$ * $N \leq L \leq 10^9$ * $0 \leq T_i \leq L-1$ * $T_i<T_{i+1}$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $L$ $T_1$ $:$ $T_N$ [samples]

Samples

Input #1

Output #1

0.414213562373095 -0.000000000000000

The three points have the coordinates $(1,0)$, $(0,1)$, and $(0,-1)$. The center of the circle inscribed in the triangle formed by these points is $(\sqrt{2}-1,0)$.

Input #2

Output #2

\-0.229401949926902 -0.153281482438188

Input #3

Output #3

0.352886583546338 -0.109065017701873

API Response (JSON)

{
  "problem": {
    "name": "Incenters",
    "description": {
      "content": "Given are $N$ points on the circumference of a circle centered at $(0,0)$ in an $xy$\\-plane. The coordinates of the $i$\\-th point are $(\\cos(\\frac{2\\pi T_i}{L}),\\sin(\\frac{2\\pi T_i}{L}))$. Three disti",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc039_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given are $N$ points on the circumference of a circle centered at $(0,0)$ in an $xy$\\-plane. The coordinates of the $i$\\-th point are $(\\cos(\\frac{2\\pi T_i}{L}),\\sin(\\frac{2\\pi T_i}{L}))$.\nThree disti...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments