凸包类
conv get_convex(vector<pt> a)
用点集求出凸包（逆时针保存）bool isconvex(const vector<pt> &a)
对给定的点集（顺逆时针均可），判断是否构成凸包bool containOn(const conv &a, const pt &b)
复杂度 O(n) 判断点b是否在凸包a的内部或边界上bool containOlogn(const conv &a, const pt &b)
复杂度 O(\log n) 判断点b是否在凸包a的内部或边界上db convex_dia(conv &a, int &fi, int &se)
返回凸包的直径，两个点分别记录在fi和se
namespace Convex {
struct conv {
vector<pt> P;
conv(int sz = 0){
P.resize(sz);
}
db cir() {
db res = 0; int n = (int)P.size();
for(int i = 0; i < n; i++) res += dist(P[i], P[nex(i)]);
return res;
}
db area() {
db sum = 0; int n = (int)P.size();
for(int i = 0; i < n; i++) sum += det(P[i], P[nex(i)]);
return sum / 2.0;
}
};
conv get_convex(vector<pt> a) {
// 若要凸包上包含共线，则下面while中的小于等于改为小于
conv res(2 * (int)a.size() + 5);
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
int m = 0, sz = (int)a.size();;
for (int i = 0; i < sz; i++) {
while (m > 1 && cmp(det(res.P[m-1] - res.P[m-2], a[i] - res.P[m-2])) <= 0) m--;
res.P[m++] = a[i];
}
int k = m;
for(int i = sz - 2; i >= 0; i--) {
while (m > k && cmp(det(res.P[m-1] - res.P[m-2], a[i] - res.P[m-2])) <= 0) m--;
res.P[m++] = a[i];
}
res.P.resize(m);
if (sz > 1) res.P.resize(m - 1);
return res;
}
bool isconvex(const vector<pt> &a) {
int n = (int)a.size();
int dir = cmp(det(a[1] - a[0], a[2] - a[1])) < 0 ? -1 : 1;
for (int i = 1; i < n; i++) {
int now = cmp(det(a[nex(i)] - a[i], a[nex(nex(i))] - a[nex(i)]));
int tmp = now < 0 ? -1 : 1;
if(tmp != dir) return false;
}
return true;
}
bool containOn(const conv &a, const pt &b) {
int n = (int)a.P.size(), sign = 0;
for (int i = 0; i < n; i++) {
int x = cmp(det(a.P[i] - b, a.P[nex(i)] - b));
if (x) {
if (sign) {if(sign != x) return false;}
else sign = x;
}
}
return true;
}
int containOlogn(const conv &a, const pt &b) {
int n = (int)a.P.size();
pt g = (a.P[0] + a.P[n / 3] + a.P[2 * n / 3]) / 3.0;
int l = 0, r = n;
while (l + 1 < r) {
int mid = (l + r) >> 1;
int dl = cmp(det(a.P[l] - g, b - g));
if (cmp(det(a.P[l] - g, a.P[mid] - g)) > 0) {
if(dl >= 0 &&
cmp(det(a.P[mid] - g, b - g)) < 0) r = mid;
else l = mid;
}
else {
if (cmp(det(a.P[l]-g, b-g)) < 0 &&
cmp(det(a.P[mid]-g, b-g)) >= 0) l = mid;
else r = mid;
}
}
r %= n;
int z = cmp(det(a.P[r]-b, a.P[l]-b)) - 1;
if (z == -2) return 1;
return z;
}
db convex_dia(conv &a, int &fi, int &se) {
vector<pt> &p = a.P;
db maxd = 0; int n = (int)p.size();
if (n == 1) {
fi = se = 0;
return maxd;
}
for (int i = 0, j = 1; i < n; i++) {
while (cmp(det(p[nex(i)] - p[i], p[j] - p[i]) -
det(p[nex(i)] - p[i], p[nex(j)] - p[i])) < 0) j = nex(j);
db d = dist(p[i], p[j]);
if (d > maxd) {
maxd = d;
fi = i; se = j;
}
d = dist(p[nex(i)], p[nex(j)]);
if (d > maxd) {
maxd = d;
fi = i; se = j;
}
}
return maxd;
}
}
using namespace Convex;
题目大意：
求 n 个点的稳定凸包（这几个点确定的凸包是唯一的）。
分析：
即凸包每条边上点的数量大于 2.
bool judge(const conv &a) {
int n = (int)a.P.size();
if (n < 6) return false;
for (int i = 0, flag = 1; i < n; i++) {
Line::line tmp1(a.P[i], a.P[nex(i)]);
Line::line tmp2(a.P[nex(i)], a.P[nex(nex(i))]);
if (!Line::parallel(tmp1, tmp2)) {
if (!flag) return false;
else flag = 0;
}
else flag = 1;
}
return true;
}
int main() {
int T; scanf("%d", &T);
while(T--) {
int n; scanf("%d", &n);
vector<pt> v; pt tmp;
for (int i = 1; i <= n; i++) {
tmp.input();
v.push_back(tmp);
}
a = get_convex(v);
if (judge(a)) puts("YES");
else puts("NO");
}
return 0;
}
闵可夫斯基和
两个图形 A,B 的闵可夫斯基和 C=A+B=\begin{Bmatrix}a+b|a\in A,b\in B\end{Bmatrix}
conv Minkowski(conv A, conv B) {
size_t n = A.P.size(), m = B.P.size();
vector<pt> v(n), w(m), x;
for (int i = 0; i < n - 1; i++) v[i] = A.P[i + 1] - A.P[i];
v[n - 1] = A.P[0] - A.P[n - 1];
for (int i = 0; i < m - 1; i++) w[i] = B.P[i + 1] - B.P[i];
w[m - 1] = B.P[0] - B.P[m - 1];
x.push_back(A.P[0] + B.P[0]);
int p = 0, q = 0;
while (p < n && q < m) {
pt tmp = det(v[p], w[q]) >= 0 ? v[p++] : w[q++];
x.push_back(x.back() + tmp);
}
while (p < n) x.push_back(x.back() + v[p++]);
while (q < m) x.push_back(x.back() + w[q++]);
return get_convex(x);
}
题目大意：
按逆时针顺序给出三个凸包点集 A,B,C，每次查询给出点 q，问是否存在点 a\in A,b\in B,c\in C 满足 q 为 Δabc 的重心。
分析：
设重心为 Q，易知 OA+OB+OC=3OQ.
对三个凸包求个和，得到 P=A+B+C=\begin{Bmatrix}a+b+c|a\in A,b\in B\,c\in C\end{Bmatrix}，然后直接判断点 3\cdot q 是否在 P 以内即可。
int main(int argc, const char * argv[]) {
int a[3];
vector<pt> _a[3];
conv A[3];
for (int i = 0; i < 3; i++) {
scanf("%d", &a[i]); _a[i].resize(a[i]);
for (auto &p : _a[i]) p.input();
A[i] = get_convex(_a[i]);
}
conv res = Minkowski(A[0], Minkowski(A[1], A[2]));
int q; scanf("%d", &q);
while (q--) {
pt x; x.input(); x = x * 3;
if (containOlogn(res, x)) puts("YES");
else puts("NO");
}
return 0;
}
题目大意：
两个凸包 A,B，移动 B，问是否还有交点。n\le 10^5,q\le 10^5
分析：
令 (a\in A,b\in B) 则移动向量 w 使得存在 b+w=a，那么 w 需要满足 w=a-b。构造闵可夫斯基和C=\begin{Bmatrix}A+(-B)\end{Bmatrix}，在输入 B 的时候横纵坐标都取反即可。
int main(int argc, const char * argv[]) {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
vector<pt> a(n), b(m);
for (int i = 0; i < n; i++) {
a[i].input();
}
for (int i = 0; i < m; i++) {
b[i].input();
b[i] = pt() - b[i];
}
conv A = get_convex(a), B = get_convex(b);
conv C = Minkowski(A, B);
while (q--) {
pt x; x.input();
if (containOlogn(C, x)) puts("1");
else puts("0");
}
return 0;
}
Similarly, tension and mental health issues can trigger or worsen erectile dysfunction cialis online without prescription