【每日一题】 广场舞

是新朋友吗？记得先点蓝字关注我哦～

题目描述

LQ市的市民广场是一个多边形，广场上铺满了大理石的地板砖。地板砖铺得方方正正，就像坐标轴纸一样。

以某四块砖相接的点为原点，地板砖的两条边为两个正方向，一块砖的边长为横纵坐标的单位长度，则所有横纵坐标都为整数的点都是四块砖的交点（如果在广场内）。 广场的砖单调无趣，却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚，都会有大批市民前来跳舞。舞者每次都会选一块完整的砖来跳舞，两个人不会选择同一块砖，如果一块砖在广场边上导致缺角或者边不完整，则没人会选这块砖。

（广场形状的例子参考：）

现在，告诉你广场的形状，请帮LQ市的市长计算一下，同一时刻最多有多少市民可以在广场跳舞？

解题思路

1

先找到所有的点 最大的横纵点和最小的横纵点，然后判断范围内的其他三个点是否在这个多边形中

2

每判断一次如果符合条件就计数加一，如不符合就重新遍历

以下图为例，我们不可能漫无边际的处理任意两个点，所以我们可以先找出所有坐标中的x，y的上下限，即图中红色虚线所围区域。之后对区域中的每个点进行判断。而如何判断一个点是不是在所围区域之内呢？这里需要用到两点式直线方程的概念，我们构成边界的点（x1,y1）(x2,y2),两两带入所判断点（x,y）的一个坐标dy，就可以求出另一个坐标dx。而求出来的坐标dx，如果在实际x的左侧，则不在范围内；反之，在范围内。

参考代码

END

感谢作者：LinYuan

原文链接

https://www.dotcpp.com/oj/problem1838.html