[ICPC 2020 Shanghai R] Sky Garden

Luogu

IDLGP9827

Time1000ms

Memory1024MB

DifficultyP4

动态规划 DP数学2020上海Special JudgeO2优化ICPC

Prof. Du and Prof. Pang plan to build a sky garden near the city of Allin. In the garden, there will be a plant maze consisting of straight and circular roads. On the blueprint of the plant maze, Prof. Du draws $n$ circles indicating the circular roads. All of them have center $(0, 0)$. The radius of the $i$-th circle is $i$. Meanwhile, Prof. Pang draws $m$ lines on the blueprint indicating the straight roads. All of the lines pass through $(0, 0)$. Each circle is divided into $2m$ parts with equal lengths by these lines. Let $Q$ be the set of the $n+m$ roads. Let $P$ be the set of all intersections of two different roads in $Q$. Note that each circular road and each straight road have two intersections. For two different points $a\in P$ and $b\in P$, we define $dis(\{a, b\})$ to be the shortest distance one needs to walk from $a$ to $b$ along the roads. Please calculate the sum of $dis(\{a, b\})$ for all $\{a, b\}\subseteq P$. ## Input The only line contains two integers $n,m~(1\le n,m\le 500)$. ## Output Output one number -- the sum of the distances between every pair of points in $P$. Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$. [samples] ## Note ![](https://cdn.luogu.com.cn/upload/image_hosting/81sxvtcp.png) $dis(p_1, p_2)=dis(p_2, p_3)=dis(p_3, p_4)=dis(p_1, p_4)=\frac{\pi}{2}$ $dis(p_1, p_5)=dis(p_2, p_5)=dis(p_3, p_5)=dis(p_4, p_5)=1$ $dis(p_1, p_3)=dis(p_2, p_4)=2$

Samples

Input #1

1 2

Output #1

14.2831853072

Input #2

2 3

Output #2

175.4159265359

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2020 Shanghai R] Sky Garden",
    "description": {
      "content": "Prof. Du and Prof. Pang plan to build a sky garden near the city of Allin. In the garden, there will be a plant maze consisting of straight and circular roads. On the blueprint of the plant maze, Pro",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9827"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Prof. Du and Prof. Pang plan to build a sky garden near the city of Allin. In the garden, there will be a plant maze consisting of straight and circular roads.\n\nOn the blueprint of the plant maze, Pro...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments