Description:

九条可怜是一个热爱读书的女孩子。

在她最近正在读的一本小说中,描述了两个敌对部落之间的故事。第一个部落有 $n$ 个人,第二个部落有 $m$ 个人,每一个人的位置可以抽象成二维平面上坐标为 $(x_i,y_i)$ 的点。

在这本书中,人们有很强的领地意识,对于平面上的任何一个点,如果它被三个来自同一部落的人形成的三角形(可能退化成一条线段)包含(包括边界),那么这一个点就属于这一个部落的领地。如果存在一个点同时在两个阵营的领地中,那么这两个部落就会为了争夺这一个点而发生战争。

常年的征战让两个部落不堪重负,因此第二个部落的族长作出了一个英明的决定,他打算选择一个向量 $(dx,dy)$ ,让所有的族人都迁徙这个向量的距离,即所有第二阵营的人的坐标都变成 $(x_i+dx,y_i+dy)$ 。

现在他计划了 $q$ 个迁徙的备选方案,他想要你来帮忙对每一个迁徙方案,计算一下在完成了迁徙之后,两个部落之间还会不会因为争夺领地而发生战争。

Input:

第一行输入三个整数 $n,m,q,$ 表示两个部落里的人数以及迁徙的备选方案数。

接下来 $n$ 行每行两个整数 $x_i,y_i $表示第一个部落里的人的坐标。

接下来 $m$ 行每行两个整数 $x_i,y_i$ 表示第二个部落里的人的坐标。

接下来 $q$ 行每行两个整数 $dx_i,dy_i$ 表示一个迁徙方案。

输入数据保证所有人的坐标两两不同。

对于 $20\%$ 的数据, $n,m\le 5,q\le 500$ 。

对于 $40\%$ 的数据, $n,m\le 50,q\le 500$ 。

对于 $70\%$ 的数据, $n,m\le 10^4,q\le 500$ 。

对于 $100\%$ 的数据,$n,m\le 10^5,q\le 10^5$ 。

对于 $100\%$ 的数据,保证 $-10^8\le x_i,y_i,dx_i,dy_i\le 10^8;n,m\ge 3$ 。所有人的坐标两两不同且对于每一个阵营,所有人都不全共线。

Output:

对于每个迁徙方案,输出一行一个整数,$0$ 表示不会发生冲突,$1$ 表示会发生冲突。

Sample Input:

4 4 3
0 0
1 0
0 1
1 1
-1 0
0 3
0 2
0 -1
0 0
2 3
0 -1

Sample Output:

1
0
1

Note:

样例 1 解释

下图为第一组方案中两个部落的私人领地,点 $(0,0)$ 同时属于两个部落,因此会发生战争。

下图为第二组方案中两个部落的私人领地,没有点同时属于两个部落,因此不会发生战争。

下图为第三组方案中两个部落的私人领地,点 $(0,0)$ 同时属于两个部落,因此会发生战争。

题目链接

题意简言之就是求得两个点集的凸包 $A\ B$ ,判断 $B$ 按照向量 $\vec{vec}$ 移动后与 $A$ 是否相交

若 $B$ 移动 $\vec{vec}$ 后与 $A$ 相交则 $A=B+\vec{vec}$ ,所以 $\vec{vec}=A-B$

即 $\vec{vec}$ 要在 $A$ 与 $-B$ 的 闵可夫斯基和

所以求出凸包 $A$ 与 $-B$ 的闵可夫斯基和的凸包与给出向量 $\vec{vec}$ 进行判断即可

AC代码:

#include <bits/stdc++.h>
typedef double db;
const db eps = 1e-9;

int Sgn(db k) { return fabs(k) < eps ? 0 : (k < 0 ? -1 : 1); }
int Cmp(db k1, db k2) { return Sgn(k1 - k2); }

struct point { db x, y; };
point operator - (point k1, point k2) { return (point){k1.x - k2.x, k1.y - k2.y}; }
point operator + (point k1, point k2) { return (point){k1.x + k2.x, k1.y + k2.y}; }
db operator * (point k1, point k2) { return k1.x * k2.x + k1.y * k2.y; }
db operator ^ (point k1, point k2) { return k1.x * k2.y - k1.y * k2.x; }
db GetDisP2P(point k1, point k2) { return sqrt((k1 - k2) * (k1 - k2)); }
db GetLen(point k) { return sqrt(k * k); }

typedef std::vector<point> poly;
poly Grahamscan(std::vector<point> p) {
  poly ret;
  if ((int)p.size() < 3) {
    for (point &v : p) ret.emplace_back(v);
    return ret;
  }
  int idx = 0;
  for (int i = 0; i < (int)p.size(); ++i)
    if (Cmp(p[i].x, p[idx].x) < 0 || (Cmp(p[i].x, p[idx].x) == 0 && Cmp(p[i].y, p[idx].y) < 0))
      idx = i;
  std::swap(p[0], p[idx]);
  std::sort(p.begin() + 1, p.end(), [&](point k1, point k2) {
    db tmp = (k1 - p[0]) ^ (k2 - p[0]);
    if (Sgn(tmp) > 0) return true;
    else if (Sgn(tmp) == 0 && Cmp(GetDisP2P(k1, p[0]), GetDisP2P(k2, p[0])) < 0) return true;
    return false;
  });
  ret.emplace_back(p[0]);
  for (int i = 1; i < (int)p.size(); ++i) {
    while ((int)ret.size() >= 2 && Sgn((ret.back() - ret[(int)ret.size() - 2]) ^ (p[i] - ret[(int)ret.size() - 2])) <= 0) ret.pop_back();
    ret.emplace_back(p[i]);
  }
  return ret;
}

poly Minkowski(const poly &k1, const poly &k2) {
  int sz1 = (int)k1.size(), sz2 = (int)k2.size();
  std::queue<point> buf1, buf2;
  for (int i = 0; i < sz1; ++i) buf1.push(k1[(i + 1) % sz1] - k1[i]);
  for (int i = 0; i < sz2; ++i) buf2.push(k2[(i + 1) % sz2] - k2[i]);
  poly ret;
  ret.push_back(k1[0] + k2[0]);
  while (!buf1.empty() && !buf2.empty()) {
    point tmp1 = buf1.front(), tmp2 = buf2.front();
    if (Sgn(tmp1 ^ tmp2) > 0) {
      ret.push_back(ret.back() + tmp1);
      buf1.pop();
    }
    else {
      ret.push_back(ret.back() + tmp2);
      buf2.pop();
    }
  }
  while (!buf1.empty()) {
    ret.push_back(ret.back() + buf1.front());
    buf1.pop();
  }
  while (!buf2.empty()) {
    ret.push_back(ret.back() + buf2.front());
    buf2.pop();
  }
  return Grahamscan(ret);
}

bool IsIn(point p, const poly &ch) {
  point base = ch[0];
  if (Sgn((p - base) ^ (ch[1] - p)) > 0 || Sgn((p - base) ^ (ch.back() - base)) < 0) return false;
  if (Sgn((p - base) ^ (ch[1] - p)) == 0 && Cmp(GetLen(p - base), GetLen(ch[1] - base)) <= 0) return true;
  int idx = std::lower_bound(ch.begin(), ch.end(), p, [&] (point k1, point k2) { return Sgn((k1 - base) ^ (k2 - base)) > 0; }) - ch.begin() - 1;
  return Sgn((ch[idx + 1] - ch[idx]) ^ (p - ch[idx])) >= 0;
}

int main() {
  int n, m, q; scanf("%d%d%d", &n, &m, &q);
  std::vector<point> p1(n), p2(m);
  for (point &v : p1) scanf("%lf%lf", &v.x, &v.y);
  for (point &v : p2) {
    scanf("%lf%lf", &v.x, &v.y);
    v.x *= -1;
    v.y *= -1;
  }
  p1 = Grahamscan(p1);
  p2 = Grahamscan(p2);
  poly ch = Minkowski(p1, p2);
  for (int i = 0; i < q; ++i) {
    point vec; scanf("%lf%lf", &vec.x, &vec.y);
    if (IsIn(vec, ch)) printf("1\n");
    else printf("0\n");
  }
  return 0;
}
Last modification:May 15th, 2019 at 02:37 pm
如果觉得我的文章对你有用,请随意赞赏