[蓝桥杯 2016 国 B] 广场舞

Luogu
IDLGP8645
Time1000ms
Memory256MB
DifficultyP5
计算几何2016数论蓝桥杯国赛
LQ 市的市民广场是一个多边形,广场上铺满了大理石的地板砖。 地板砖铺得方方正正,就像坐标轴纸一样。 以某四块砖相接的点为原点,地板砖的两条边为两个正方向,一块砖的边长为横纵坐标的单位长度,则所有横纵坐标都为整数的点都是四块砖的交点(如果在广场内)。 广场的砖单调无趣,却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚,都会有大批市民前来跳舞。 舞者每次都会选一块完整的砖来跳舞,两个人不会选择同一块砖,如果一块砖在广场边上导致缺角或者边不完整,则没人会选这块砖。 (广场形状的例子参考图) ![](https://cdn.luogu.com.cn/upload/image_hosting/kjgaxse9.png) 现在,告诉你广场的形状,请帮 LQ 市的市长计算一下,同一时刻最多有多少市民可以在广场跳舞。 ## Input 输入的第一行包含一个整数 $n$,表示广场是 $n$ 边形的(因此有 $n$ 个顶点)。 接下来 $n$ 行,每行两个整数,依次表示 $n$ 边形每个顶点的坐标(也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。 ## Output 输出一个整数,表示最多有多少市民可以在广场跳舞。 [samples] ## Note **【样例说明】** 广场如图所示,一共有 $7$ 块完整的地板砖,因此最多能有 $7$ 位市民一起跳舞。 **【数据规模与约定】** 对于 $30\%$ 的数据,$n$ 不超过 $100$,横纵坐标的绝对值均不超过 $100$。 对于 $50\%$ 的数据,$n$ 不超过 $1000$,横纵坐标的绝对值均不超过 $1000$。 对于 $100\%$ 的数据,$n$ 不超过 $1000$,横纵坐标的绝对值均不超过 $10^8$。 时限 1 秒, 256M。蓝桥杯 2016 年第七届
Samples
Input #1
5
3 3
6 4
4 1
1 -1
0 4
Output #1
7
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2016 国 B] 广场舞",
    "description": {
      "content": "LQ 市的市民广场是一个多边形,广场上铺满了大理石的地板砖。 地板砖铺得方方正正,就像坐标轴纸一样。 以某四块砖相接的点为原点,地板砖的两条边为两个正方向,一块砖的边长为横纵坐标的单位长度,则所有横纵坐标都为整数的点都是四块砖的交点(如果在广场内)。 广场的砖单调无趣,却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚,都会有大批市民前来跳舞。 舞者每次都会选一块完整的砖来跳舞,两个人不会选",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8645"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "LQ 市的市民广场是一个多边形,广场上铺满了大理石的地板砖。\n\n地板砖铺得方方正正,就像坐标轴纸一样。\n\n以某四块砖相接的点为原点,地板砖的两条边为两个正方向,一块砖的边长为横纵坐标的单位长度,则所有横纵坐标都为整数的点都是四块砖的交点(如果在广场内)。\n\n广场的砖单调无趣,却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚,都会有大批市民前来跳舞。\n\n舞者每次都会选一块完整的砖来跳舞,两个人不会选...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments