第一次做像点样子的计算几何吧……

很显然要包含在某个三角形里，就要被包含在大点的凸包里。所以求出大点组成的凸包，然后对于所有小点判断它是否在那个凸包里即可。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <deque>
#include <cmath>
#include <vector>
using R = double;
const R eps = 1e-8;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x < 0) return -1;
    else return 1;
  }
}
struct Point {
  R x, y;
  Point(R qx = 0, R qy = 0) {
    x = qx; y = qy;
  }
};
typedef Point Vector;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
R dot(const Vector &a, const Vector &b) {
  return a.x * b.x + a.y * b.y;
}
R times(const Vector &a, const Vector &b) {
  return a.x * b.y - a.y * b.x;
}
bool cmp(const Point &a, const Point &b) {
  if(sign(a.x - b.x) == 0) {
    return a.y < b.y;
  } else {
    return a.x < b.x;
  }
}
const int maxn = 10005;
Point P[maxn]; int L;
std::vector<Point> bot, top;
void andrew() {
  // bot.resize(L); top.resize(L);
  std::sort(P + 1, P + 1 + L, cmp);
  for(int i = 1; i <= L; i ++) {
    if(i != 1 && sign(P[i].x - P[i - 1].x) == 0) continue;
    while(bot.size() > 1 && sign(times(P[i] - bot.back(), bot.back() - bot[bot.size() - 2])) >= 0) {
      bot.pop_back();
    }
    bot.push_back(P[i]);
  }
  for(int i = L; i >= 1; i --) {
    if(i != L && sign(P[i].x - P[i + 1].x) == 0) continue;
    while(top.size() > 1 && sign(times(P[i] - top.back(), top.back() - top[top.size() - 2])) >= 0) {
      top.pop_back();
    }
    top.push_back(P[i]);
  }
  std::reverse(top.begin(), top.end());
#ifdef LOCAL
  printf("top :");
  for(auto p : top) {
    printf(" (%.3f, %.3f)", p.x, p.y);
  }
  puts("");
  printf("bot :");
  for(auto p : bot) {
    printf(" (%.3f, %.3f)", p.x, p.y);
  }
  puts("");
#endif
}
R get_p(Point l, Point r, R x) {
  R delta = x - l.x;
  R k = (r.y - l.y) / (r.x - l.x);
#ifdef LOCAL
  printf("k between (%.2lf, %.2lf) and (%.2lf, %.2lf) : %.5lf\n", l.x, l.y, r.x, r.y, k);
#endif
  return l.y + k * delta;
}
bool cmp2(const Point &a, const Point &b) {
  return sign(a.x - b.x) == -1;
}
bool query(const Point &p) {
  if(sign(top.front().x - p.x) == 1 || sign(p.x - top.back().x) == 1) return false;
  auto lp = (std::lower_bound(bot.begin(), bot.end(), p, cmp2));
  auto rp = (std::lower_bound(top.begin(), top.end(), p, cmp2));
  R l;
  if(sign((*lp).x - p.x) == 0) {
    l = (*lp).y;
  } else {
    auto lp2 = lp - 1;
    l = get_p(*lp2, *lp, p.x);
  }
  R r;
  if(sign((*rp).x - p.x) == 0) {
    r = (*rp).y;
  } else {
    auto rp2 = rp - 1;
    r = get_p(*rp2, *rp, p.x);
  }
#ifdef LOCAL
  printf("bd of (%.2lf, %.2lf) : [%.2lf, %.2lf]\n", p.x, p.y, l, r);
#endif
  return (sign(l - p.y) <= 0 && sign(p.y - r) <= 0);
}

int main() {
  scanf("%d", &L);
  for(int i = 1; i <= L; i ++) {
    scanf("%lf%lf", &P[i].x, &P[i].y);
  }
  andrew();
  int S; scanf("%d", &S);
  int cnt = 0;
  while(S --) {
    R x, y; scanf("%lf%lf", &x, &y);
    Point p(x, y);
    if(query(p)) cnt ++;
  }
  printf("%d\n", cnt);
  return 0;
}

• 相关文章
• 全局相关文章