{"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舞者每次都会选一块完整的砖来跳舞，两个人不会选择同一块砖，如果一块砖在广场边上导致缺角或者边不完整，则没人会选这块砖。\n\n（广场形状的例子参考图）\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/kjgaxse9.png)\n\n现在，告诉你广场的形状，请帮 LQ 市的市长计算一下，同一时刻最多有多少市民可以在广场跳舞。\n\n## Input\n\n输入的第一行包含一个整数 $n$，表示广场是 $n$ 边形的（因此有 $n$ 个顶点）。\n\n接下来 $n$ 行，每行两个整数，依次表示 $n$ 边形每个顶点的坐标（也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。\n\n## Output\n\n输出一个整数，表示最多有多少市民可以在广场跳舞。\n\n[samples]\n\n## Note\n\n**【样例说明】**\n\n广场如图所示，一共有 $7$ 块完整的地板砖，因此最多能有 $7$ 位市民一起跳舞。\n\n**【数据规模与约定】**\n\n对于 $30\\%$ 的数据，$n$ 不超过 $100$，横纵坐标的绝对值均不超过 $100$。\n\n对于 $50\\%$ 的数据，$n$ 不超过 $1000$，横纵坐标的绝对值均不超过 $1000$。\n\n对于 $100\\%$ 的数据，$n$ 不超过 $1000$，横纵坐标的绝对值均不超过 $10^8$。\n\n时限 1 秒, 256M。蓝桥杯 2016 年第七届","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8645","tags":["计算几何","2016","数论","蓝桥杯国赛"],"sample_group":[["5\n3 3\n6 4\n4 1\n1 -1\n0 4","7"]],"created_at":"2026-03-03 11:09:25"}}