A40843. 广场舞
填空题
困难
知识点
题目描述
广场舞
题目描述
LQ市的市民广场是一个多边形，广场上铺满了大理石的地板砖。
地板砖铺得方方正正，就像坐标轴纸一样。
以某四块砖相接的点为原点，地板砖的两条边为两个正方向，一块砖的边长为横纵坐标的单位长度，则所有横纵坐标都为整数的点都是四块砖的交点（如果在广场内）。
广场的砖单调无趣，却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚，都会有大批市民前来跳舞。
舞者每次都会选一块完整的砖来跳舞，两个人不会选择同一块砖，如果一块砖在广场边上导致缺角或者边不完整，则没人会选这块砖。现在，告诉你广场的形状，请帮LQ市的市长计算一下，同一时刻最多有多少市民可以在广场跳舞。
输入格式
输入的第一行包含一个整数n，表示广场是n边形的（因此有n个顶点）。
接下来n行，每行两个整数，依次表示n边形每个顶点的坐标（也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。
输出格式
输出一个整数，表示最多有多少市民可以在广场跳舞。
样例输入
5
3 3
6 4
4 1
1 -1
0 4
样例输出
7
参考答案
#include<iostream>
#include<algorithm>
using namespace std;
struct side {
double x1;
double x2;
double y1;
double y2;
double k;
double b;
bool flag = true;
};
struct point {
double x;
double y;
};
int sum = 0;
bool inside_con(point *p, int num, side *s, point *p_old)
{
sum = 0;
double tmp_x, tmp_y, tmp_y1, tmp_y2, tmp, tmp_x1, tmp_x2;
for (int i = 0; i<num; i++)
{
for (int j = 0; j < num; j++)
{
if (p->x == p_old[j].x && p->y == p_old[j].y) return true;
}
tmp_y1 = s[i].y1;
tmp_y2 = s[i].y2;
tmp_x1 = s[i].x1;
tmp_x2 = s[i].x2;
if (tmp_y1 > tmp_y2) //交换y1和y2，使得y2>y1
{
tmp = tmp_y1;
tmp_y1 = tmp_y2;
tmp_y2 = tmp;
}
if (tmp_x1 > tmp_x2) //交换x1和x2，使得x2>x1
{
tmp = tmp_x1;
tmp_x1 = tmp_x2;
tmp_x2 = tmp;
}
//以下为考虑各种情况,此情况为k不存在
if (s[i].flag == false)
{
tmp_x = s[i].x1;
tmp_y = p->y;
if (tmp_x < p->x && tmp_y <= tmp_y2 && tmp_y > tmp_y1)
{
sum++;
}
}
else
{
if (s[i].k == 0 && p->x <= tmp_x2 && p->x >= tmp_x1 && p -> y == tmp_y1)
{
return true;
}
else if (s[i].k != 0)
{
tmp_x = (p->y - s[i].b) / s[i].k;
tmp_y = s[i].k*tmp_x + s[i].b;
if (tmp_x == p->x && tmp_y == p->y && tmp_y < tmp_y2 && tmp_y > tmp_y1)
{
return true;
}
if (tmp_x<p->x && tmp_y <= tmp_y2 && tmp_y > tmp_y1)
{
sum++;
}
}
}
}
if (sum == 0)
{
return false;
}
else if (sum % 2 == 0)
{
return false;
}
else
{
return true;
}
}
void find(point *p, int num, int *x_max, int *y_max ,int *x_min, int *y_min)
{
double *x = new double[num];
double *y = new double[num];
for (int i = 0; i < num; i++)
{
x[i] = p[i].x;
y[i] = p[i].y;
}
sort(x, x + num);
sort(y, y + num);
*x_min = int(x[0]);
*x_max = int(x[num - 1]);
*y_min = int(y[0]);
*y_max = int(y[num - 1]);
}
int main()
{
int num;
cin >> num;
point *p = new point[num];
for (int i = 0; i<num; i++)
{
cin >> p[i].x >> p[i].y;
}
side *s = new side[num];
for (int i = 0; i<num; i++)
{
if (i<num - 1)
{
s[i].x1 = p[i].x;
s[i].x2 = p[i + 1].x;
s[i].y1 = p[i].y;
s[i].y2 = p[i + 1].y;
//求斜率
if (s[i].x1 == s[i].x2)
{
s[i].flag = false;
}
else
{
s[i].k = (s[i].y1 - s[i].y2) / (s[i].x1 - s[i].x2);
s[i].b = s[i].y1 - s[i].k*s[i].x1;
}
}
else if (i == num - 1)
{
s[i].x1 = p[i].x;
s[i].x2 = p[0].x;
s[i].y1 = p[i].y;
s[i].y2 = p[0].y;
//求斜率
if (s[i].x1 == s[i].x2)
{
s[i].flag = false;
}
else
{
s[i].k = (s[i].y1 - s[i].y2) / (s[i].x1 - s[i].x2);
s[i].b = s[i].y1 - s[i].k*s[i].x1;
}
}
}
point *real_p = new point;
point *test_p = new point;
int x_min, x_max, y_min, y_max;
find(p, num, &x_max, &y_max, &x_min, &y_min);
//cout << x_min << " " << x_max << " " << y_min << " " << y_max << endl << endl;
bool flag1, flag2, flag3, flag4;
int sum_num = 0;
for (int i = x_min; i <= x_max; i++)
{
for (int j = y_min; j <= y_max; j++)
{
real_p->x = i; real_p->y = j;
flag1 = inside_con(real_p, num, s, p);
//cout << real_p->x << " " << real_p->y << endl;
//if (flag1 == true) cout << "在多边形中";
//else cout << "不在多边形中";
//cout << endl << sum << endl << endl;
real_p->x = i; real_p->y = j + 1;
flag2 = inside_con(real_p, num, s, p);
//cout << real_p->x << " " << real_p->y << endl;
//if (flag2 == true) cout << "在多边形中";
//else cout << "不在多边形中";
//cout << endl << sum << endl << endl;
real_p->x = i + 1; real_p->y = j;
flag3 = inside_con(real_p, num, s, p);
//cout << real_p->x << " " << real_p->y << endl;
//if (flag3 == true) cout << "在多边形中";
//else cout << "不在多边形中";
//cout << endl << sum << endl << endl;
real_p->x = i + 1; real_p->y = j + 1;
flag4 = inside_con(real_p, num, s, p);
//cout << real_p->x << " " << real_p->y << endl;
//if (flag4 == true) cout << "在多边形中";
//else cout << "不在多边形中";
//cout << endl << sum << endl << endl;
if (flag1 == true && flag2 == true && flag3 == true && flag4 == true)
{
sum_num++;
}
}
}
cout << sum_num;
//test_p->x = 5;
//test_p->y = 1;
//if (inside_con(test_p, num, s, p) == true) cout << "在多边形中";
//else cout << "不在多边形中";
//cout << endl << sum;
}答案解析
上一题
下一题