求出的点集是无序的，在求凸包时极角排序了
by an_ancient_ghoul @ 2023-07-24 11:06:30
[顺便帮帮我吧](https://www.luogu.com.cn/discuss/641901)
by an_ancient_ghoul @ 2023-07-24 11:48:55
@[an_ancient_ghoul](/user/644509) 不对哦，minkow 的点集应当是有序的。
可以参考代码：
```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
using lint = long long;
const int N = 2e5 + 7;
const double eps = 1e-12;
int dcmp(double x, double y) {
if (x - y > eps) return 1;
if (y - x > eps) return -1;
return 0;
}
struct Point {
lint x, y;
Point operator + (const Point &p) const {
return {x + p.x, y + p.y};
}
Point operator - (const Point &p) const {
return {x - p.x, y - p.y};
}
lint operator ^ (const Point &p) const {
return x * p.y - y * p.x;
}
double angle() const {
return ::atan2(y, x);
}
} A[N], B[N], minkow[N];
bool slopeCmp(const Point &l, const Point &m, const Point &r) {
return ((r - l) ^ (m - l)) > 0;
}
int convexHull(Point *ps, int n) {
for (int i = 1; i < n; ++i) {
if (ps[i].x < ps[0].x || (ps[i].x == ps[0].x && ps[i].y < ps[0].y))
swap(ps[i], ps[0]);
}
sort(ps + 1, ps + n, [&](const Point &l, const Point &r) {
double al = (l - ps[0]).angle(), ar = (r - ps[0]).angle();
return !dcmp(al, ar) ? (l.x ^ r.x ? l.x < r.x : l.y < r.y) : al < ar;
});
static Point stk[N]; int top = 0;
for (int i = 0; i < n; ++i) {
while (top > 1 && slopeCmp(stk[top - 2], stk[top - 1], ps[i]))
--top;
stk[top++] = ps[i];
}
for (int i = 0; i < top; ++i)
ps[i] = stk[i];
return top;
}
int Minkowski(Point *pa, Point *pb, int n, int m) {
static Point ta[N], tb[N];
for (int i = 0; i < n; ++i)
ta[i] = pa[(i + 1) % n] - pa[i];
for (int i = 0; i < m; ++i)
tb[i] = pb[(i + 1) % m] - pb[i];
int idx = 0, i = 0, j = 0;
minkow[idx++] = pa[0] + pb[0];
while (i < n || j < m) {
if (j == m || (i < n && (ta[i] ^ tb[j]) >= 0))
minkow[idx++] = ta[i++];
else
minkow[idx++] = tb[j++];
}
for (int i = 1; i < idx; ++i)
minkow[i] = minkow[i] + minkow[i - 1];
return idx;
}
int checkIn(const Point *cvx, int c, const Point &vec) {
if ((vec ^ cvx[0]) > 0 || (cvx[c - 1] ^ vec) > 0) return 0;
int lt = 0;
for (int w = 1 << (int)log2(c); w; w >>= 1) {
if (lt + w < c && (cvx[lt + w] ^ vec) > 0)
lt += w;
}
return ((cvx[lt + 1] - cvx[lt]) ^ (vec - cvx[lt])) >= 0;
}
int main(void) {
cin.tie(0)->sync_with_stdio(false);
int n, m, q;
cin >> n >> m >> q;
lint x, y;
for (int i = 0; i < n; ++i) {
cin >> x >> y;
A[i] = {x, y};
}
for (int i = 0; i < m; ++i) {
cin >> x >> y;
B[i] = {-x, -y};
}
n = convexHull(A, n);
m = convexHull(B, m);
int c = Minkowski(A, B, n, m);
// c = convexHull(minkow, c);
Point O = minkow[0];
for (int i = 0; i < c; ++i)
minkow[i] = minkow[i] - O;
for (int i = 0; i < q; ++i) {
lint x, y; cin >> x >> y;
cout << checkIn(minkow, c, (Point){x, y} - O) << '\n';
}
return 0;
}
```
这是可以 $\texttt{\colorbox{#52C41A}{\textcolor{white}{AC}}}$ 的。
by aish @ 2023-07-24 20:43:03
@[aish](/user/939357) 好的，大佬能否帮帮在下
by an_ancient_ghoul @ 2023-07-24 21:01:00
@[The_Last_Candy](/user/431150) 所以你的程序为什么会WA啊
by Asadcle015 @ 2023-10-21 17:05:31
因为会有一些多余的点。刚才调的时候输出发现的
by Swidish_Pigeon @ 2024-02-23 00:36:14
@aish，您给出的代码在下面这组数据会出错
```
input:
5 5 1
-15 39
1 12
-15 -2
2 5
-40 -30
14 34
-10 -15
14 11
1 -44
13 -24
24 1
output:
0
```
by coldicy @ 2024-05-16 18:19:42