广场舞

本文主要是介绍广场舞，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

LQ市的市民广场是一个多边形，广场上铺满了大理石的地板砖。

地板砖铺得方方正正，就像坐标轴纸一样。
以某四块砖相接的点为原点，地板砖的两条边为两个正方向，一块砖的边长为横纵坐标的单位长度，
则所有横纵坐标都为整数的点都是四块砖的交点（如果在广场内）。

广场的砖单调无趣，却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚，都会有大批市民前来跳舞。
舞者每次都会选一块完整的砖来跳舞，两个人不会选择同一块砖，如果一块砖在广场边上导致缺角或者边不完整，则没人会选这块砖。
（广场形状的例子参考【图1.png】）

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

【输入格式】
输入的第一行包含一个整数n，表示广场是n边形的（因此有n个顶点）。
接下来n行，每行两个整数，依次表示n边形每个顶点的坐标（也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。

【输出格式】
输出一个整数，表示最多有多少市民可以在广场跳舞。

【样例输入】
5
3 3
6 4
4 1
1 -1
0 4

【样例输出】
7

【样例说明】
广场如图1.png所示，一共有7块完整的地板砖，因此最多能有7位市民一起跳舞。

【数据规模与约定】
对于30%的数据，n不超过100，横纵坐标的绝对值均不超过100。
对于50%的数据，n不超过1000，横纵坐标的绝对值均不超过1000。
对于100%的数据，n不超过1000，横纵坐标的绝对值均不超过100000000（一亿）。
这里写图片描述
第七届蓝桥杯决赛B组第5题

分析

简单的小学几何，首先以人的思维方式，通过从上到下从左到右完整的数有几个小正方形，但是转化为电脑首先我要计算一个点是否在多边形内，如果该点位于多边形内，那么考虑与该点相邻的右点，下点以及对角点是否存在于多边形内，如果四个点均位于多边形内，那么这四个点构成小正方形，想法是不是很简单啊？如何判断呢？
首先我们要得到x，y的边界值，如果不在边界范围内的值，肯定不会构成小正方形；
然后从边界对每一个点开始扫描，根据是否能构成小正方形
这样是不是很简单了

代码

废话少说直接上代码

#include<iostream>
using namespace std;//待输入的点的坐标
float vxx[100];
float vyy[100];
int num;//多边形//判断是否在多边形边上和内部
//判断点是否在多边形内
/*
bool IsInPolygon(int x, int y, int vertex[][2], int num)
{if (num < 3)return false;//两点构成直线int cnt = 0;for (int i = 0; i < num; i++){int p1[2] = { vertex[i][0],vertex[i][1] };//当前的点int p2[2] = { vertex[(i + 1) % num][0],vertex[(i + 1) % num][1] };//与之相邻的点  构成封闭图形if (p2[1] == p1[1]&&p2[0]==p1[0])continue;//继续循环if (y < p2[1] && y < p1[1])//上下有问题continue;if (y > p2[1] && y > p1[1])continue;//y在内部int xx = (y - p1[1])* (p2[0] - p1[0]) / (p2[1] - p1[1]) + p1[0];if (xx >= x)cnt++;}return (cnt % 2 == 1);
}*///nvert 表示多边形的点的个数   
//vertx[]  verty[]  多边形各个顶点所在的位置  testx  testy带判断的点的坐标值
//在四边形内是1 不在是0 包括边线上的点
int pnpoly(int nvert, float vertx[], float verty[], float testx, float testy)
{for (int k = 0; k < nvert; k++)//遍历全部顶点{//待判断的点为多边形的顶点，即点属于多边形if (testx == vertx[k] && testy == verty[k])return 1;}//多边形边上的点平行于x轴for (int i = 0; i < num; i++){//多边形内的任意点 以及与之相连接的下一个点 x y坐标的偏移量float dy = verty[(i + 1) % num] - verty[i];float dx = vertx[(i + 1) % num] - vertx[i];float k = dy / dx;//某边的斜率//待测点与当前点的斜率if (((verty[i] - testy) / (vertx[i] - testx)) == k((testx>vertx[i]&&testx<vertx[(i+1)%num])|| testx<vertx[i] && testx>vertx[(i + 1) % num])))return 1;//if (testy == verty[i] && verty[(i + 1) % num] == verty[i] && testy == verty[(i + 1) % num])return 1;}//平行于y轴for (int i = 0; i < num; i++){//同一条直线上if (testx == vertx[i] && vertx[(i + 1) % num] == vertx[i]&&((testy<verty[i]&&testy>verty[(i+1)%num])|| (testy>verty[i] && testy<verty[(i + 1) % num])))return 1;}int i, j, c = 0;for (i = 0, j = nvert - 1; i < nvert; j = i++)//多边形内的{if (((verty[i]>testy) != (verty[j]>testy)) &&(testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]))c = !c;}return c;
}//找出边的上下左右边界，即x max min   y max min
bool IsSquare(int x, int y)
{if (pnpoly(num, vxx, vyy, x, y) == 1)//当前的点在多边形上{if (pnpoly(num, vxx, vyy, x + 1, y) == 0)return false;//左边的点if (pnpoly(num, vxx, vyy, x, y - 1) == 0)return false;//下边的点if (pnpoly(num, vxx, vyy, x + 1, y - 1) == 0)return false;//对角的点cout << x << "," << y << endl;//输出每个小正方形的左上角return true;}elsereturn false;
}/*心型数据
6
1 3
2 4
3 3
4 4
5 3
3 -1
*/int main()
{int cnt = 0;cin >> num;//输入多边形的个数for (int i = 0; i < num; i++){cin >> vxx[i] >> vyy[i];}//得到图形的边界   即 x的左右边界  y的上下边界float xMax = vxx[0], xMin = vxx[0], yMax = vyy[0], yMin = vyy[0];for (int i = 0; i < num; i++){if (vxx[i] > xMax)xMax = vxx[i];if (vxx[i] < xMin)xMin = vxx[i];if (vyy[i] > yMax)yMax = vyy[i];if (vyy[i] < yMin)yMin = vyy[i];}//扫描函数  得到  x 取值范围   y取值范围cout << "xMax=" << xMax << ",xMin=" << xMin << ",yMax=" << yMax << ",yMin=" << yMin << endl;//扫描函数依次判断for (float x = xMin; x <= xMax; x++){for (float y = yMax; y >= yMin; y--){//是否构成小正方形if (IsSquare(x, y) == true)cnt++;if (pnpoly(num, vxx, vyy, x, y) == 1)cout << "(" << x << "," << y << ")" << endl;}}cout << "共"<<cnt<<"个小正方形" << endl;return 0;
}