CF55E-Very-Simple-Problem

讲道理的话，题目中有simple一词的题目都不会简单。。

这道题如果我们直接计算包含的个数，本蒟蒻只能想到$O(n^3)$的解法，然后就咕咕了。。于是我们可以从反面考虑——数不包含该点的三角形。然后我们发现，如果一个三角形不包含该点，则这个三角形总有一条边把该点和三角形另一个顶点分割开了，于是我们只需要枚举线段那个分割线段，然后求三角形另一个顶点有多少种选法即可，最后用总数减一下。

上代码：

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100005;

pair<long long, long long> a[2 * MAX_N];

inline long long dis(long long x1, long long y1, long long x2, long long y2,
                     long long x3, long long y3) {
  return (x2 - x1) * (y3 - y2) - (y2 - y1) * (x3 - x2);
}

inline bool in_poly(long long x, long long y, int n) {
  long long area1 = 0, area2 = 0;
  for (int i = 1; i <= n; ++i)
    area1 += a[i].first * a[i + 1].second - a[i].second * a[i + 1].first;
  for (int i = 1; i <= n; ++i)
    area2 += fabs(
        dis(x, y, a[i].first, a[i].second, a[i + 1].first, a[i + 1].second));
  return fabs(area) == area2;
}

long long C3(int x) {
  if (x < 3)
    return 0;
  return 1LL * x * (x - 1) * (x - 2) / 6;
}

long long C2(int x) {
  if (x < 2)
    return 0;
  return 1LL * x * (x - 1) / 2;
}

long long solve(long long x, long long y, int n) {
  if (!in_poly(x, y, n))
    return 0;
  int j = 2;
  long long sum = 0;
  for (int i = 1; i <= n; ++i) {
    for (; dis(a[i].first, a[i].second, a[j + 1].first, a[j + 1].second, x, y) <
           0;
         ++j)
      ;
    sum += C2(j - i);
  }
  return C3(n) - sum;
}

int main() {
  int n, t;
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> a[i].first >> a[i].second;
  for (int i = 1; i < n; ++i)
    a[i + n] = a[i];
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    long long x, y;
    cin >> x >> y;
    cout << solve(x, y, n) << "\n";
  }
  return 0;
}