本文主要是介绍uva 11168 凸包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
void getLineGeneralEquation(const Point& p1, const Point& p2, double& a, double& b, double &c)
{a = p2.y - p1.y;b = p1.x - p2.x;c = -a * p1.x - b * p1.y;
}
把直线的两点式转化为一般式，恩，没什么要注意的。
#include <bits/stdc++.h>
using namespace std;
struct Point
{double x, y;Point(double x = 0, double y = 0): x(x), y(y) { }
};typedef Point Vector;Vector operator - (const Point& A, const Point& B)
{return Vector(A.x - B.x, A.y - B.y);
}double Cross(const Vector& A, const Vector& B)
{return A.x * B.y - A.y * B.x;
}bool operator < (const Point& p1, const Point& p2)
{return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}bool operator == (const Point& p1, const Point& p2)
{return p1.x == p2.x && p1.y == p2.y;
}
vector<Point> ConvexHull(vector<Point> p)
{// 预处理，删除重复点sort(p.begin(), p.end());p.erase(unique(p.begin(), p.end()), p.end());int n = p.size();int m = 0;vector<Point> ch(n + 1);for (int i = 0; i < n; i++){while (m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--;ch[m++] = p[i];}int k = m;for (int i = n - 2; i >= 0; i--){while (m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--;ch[m++] = p[i];}if (n > 1) m--;ch.resize(m);return ch;
}
void getLineGeneralEquation(const Point& p1, const Point& p2, double& a, double& b, double &c)
{a = p2.y - p1.y;b = p1.x - p2.x;c = -a * p1.x - b * p1.y;
}
int T, N, kase;
double x, y, A, B, C;
int main(int argc, char const *argv[])
{scanf("%d", &T);while (T--){scanf("%d", &N);vector<Point>P;double sumx = 0, sumy = 0, ans = 1E9;for (int i = 0; i < N; i++){scanf("%lf%lf", &x, &y);sumx += x, sumy += y;P.push_back(Point(x, y));}vector<Point>ch = ConvexHull(P);if (ch.size() <= 2) ans = 0;else for (int i = 0; i < ch.size(); i++){getLineGeneralEquation(ch[i], ch[(i + 1) % ch.size()], A, B, C);ans = min(ans, fabs(A * sumx + B * sumy + C * N) / sqrt(A * A + B * B));}printf("Case #%d: %.3lf\n", ++kase, ans / N);}return 0;
}所有点在该直线的同一侧，明显是直接利用凸包的边更优。所以枚举凸包的每一条边，然后求距离和。
把两点式转化为一般式后，不必循环啦，把所有的x和y分别加起来，带入方程就好了。
这篇关于uva 11168 凸包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
