1 条题解
-
0
题意分析
题目大意是:给定平面上的一些树(点),要用这些树作为围栏的顶点,围出一个尽可能大的牧场。牧场的面积决定了可以放多少头牛,每头牛至少需要50平方米的牧场面积。要求计算这个最大牧场能放多少头牛。
解题思路
- 凸包(Convex Hull):首先需要找到这些点的凸包,因为凸包能够围出最大的面积。凸包是指包含所有点的最小凸多边形。
- 计算凸包面积:计算凸包所围成的多边形的面积。
- 计算牛的数量:将面积除以50,取整数部分即可得到牛的数量。
代码实现
代码使用了Andrew算法(或称为Graham扫描法)来求凸包,然后通过叉积计算凸包的面积。具体步骤如下:
- 输入处理:读取所有点的坐标,并找到最左下角的点作为凸包的起点。
- 极角排序:将其他点按照与起点的极角进行排序,如果极角相同,则按距离排序。
- 构建凸包:使用栈结构来维护凸包的点,确保每次新加入的点不会破坏凸包的凸性。
- 计算面积:利用叉积的性质计算凸包的面积。叉积的绝对值等于两个向量所夹平行四边形的面积,因此多边形的面积可以通过将多边形分割成多个三角形来计算。
- 输出结果:将面积除以50,取整数部分输出。
标程
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int maxn = 10005; const double PI = acos(-1.0); struct Point { int x, y; Point() : x(0), y(0) {} Point(int x, int y) : x(x), y(y) {} } list[maxn]; int stack[maxn], top; // 计算叉积 p0p1 × p0p2 int cross(Point p0, Point p1, Point p2) { return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y); } // 计算 p1p2 的距离 double dis(Point p1, Point p2) { return sqrt((double)(p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y)); } // 极角排序函数,角度相同则距离小的在前面 bool cmp(Point p1, Point p2) { int tmp = cross(list[0], p1, p2); if (tmp > 0) return true; else if (tmp == 0 && dis(list[0], p1) < dis(list[0], p2)) return true; else return false; } // 输入,把最左下角放在 list[0],并且进行极角排序 void init(int n) { Point p0; scanf("%d%d", &list[0].x, &list[0].y); p0.x = list[0].x; p0.y = list[0].y; int k = 0; for (int i = 1; i < n; ++i) { scanf("%d%d", &list[i].x, &list[i].y); if ((p0.y > list[i].y) || ((p0.y == list[i].y) && (p0.x > list[i].x))) { p0.x = list[i].x; p0.y = list[i].y; k = i; } } list[k] = list[0]; list[0] = p0; sort(list + 1, list + n, cmp); } // graham扫描法求凸包,凸包顶点存在 stack 栈中 void graham(int n) { if (n == 1) { top = 0; stack[0] = 0; return; } top = 1; stack[0] = 0; stack[1] = 1; for (int i = 2; i < n; ++i) { while (top > 0 && cross(list[stack[top - 1]], list[stack[top]], list[i]) <= 0) --top; stack[++top] = i; } } int main() { int n; while (~scanf("%d", &n)) { if (n < 3) { // 至少需要3个点才能围成多边形 printf("0\n"); continue; } init(n); graham(n); if (top < 2) { // 如果凸包的点数小于3,无法围成多边形 printf("0\n"); continue; } int area = 0; for (int i = 1; i < top; ++i) { area += cross(list[stack[0]], list[stack[i]], list[stack[i + 1]]); } area = abs(area) / 2; printf("%d\n", area / 50); } return 0; }
代码解释
- 数据结构:使用
Point
结构体存储点的坐标。 - 叉积计算:
cross
函数计算三个点的叉积,用于判断点的相对位置。 - 距离计算:
dis
函数计算两点之间的距离。 - 极角排序:
cmp
函数用于对点进行极角排序,确保凸包的正确构建。 - 凸包构建:
init
函数初始化点集并排序,graham
函数使用栈构建凸包。 - 面积计算:通过叉积的累加和计算凸包的面积,注意取绝对值并除以2得到实际面积。
- 输出结果:将面积除以50得到牛的数量并输出。
该程序能够高效地处理最多10000个点,并正确计算出最大牧场的面积及可容纳的牛的数量。
- 1
信息
- ID
- 2349
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者