G49 向量运算 点线关系【计算几何】

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

const int N = 10010;
struct Point
{
  long long x, y;
} a[N], b[N], p;
int n, m, ans[N];

long long cross(Point a, Point b, Point c)
{ // 叉积
  return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int find(Point p)
{ // 二分
  int l = -1, r = n + 1;
  while (l + 1 < r)
  {
    int mid = l + r >> 1;
    if (cross(b[mid], a[mid], p) <= 0)
      l = mid;
    else
      r = mid;
  }
  return l;
}
int main()
{
  long long x1, y1, x2, y2, u, l;
  bool num1 = 1;
  while (scanf("%d", &n), n)
  {
    scanf("%d%lld%lld%lld%lld", &m, &x1, &y1, &x2, &y2);
    a[0].x = x1, a[0].y = y1;
    b[0].x = x1, b[0].y = y2; // 左边界
    for (int i = 1; i <= n; i++)
    {
      scanf("%lld%lld", &u, &l);
      a[i].x = u, a[i].y = y1;
      b[i].x = l, b[i].y = y2; // 纸板端点
    }
    memset(ans, 0, sizeof ans);
    while (m--)
    {
      scanf("%lld%lld", &p.x, &p.y); // 玩具坐标
      ans[find(p)]++;                // 二分答案
    }
    num1 ? num1 = 0 : puts(""); // 第一行不输出空行
    for (int i = 0; i <= n; i++)
      printf("%d: %d\n", i, ans[i]);
  }
  return 0;
}

G49 向量运算 点线关系【计算几何】

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

const int N = 10010;
struct Point
{
  long long x, y;
} a[N], b[N], p;
int n, m, ans[N];

long long cross(Point a, Point b, Point c)
{ // 叉积
  return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int find(Point p)
{ // 二分
  int l = -1, r = n + 1;
  while (l + 1 < r)
  {
    int mid = l + r >> 1;
    if (cross(b[mid], a[mid], p) <= 0)
      l = mid;
    else
      r = mid;
  }
  return l;
}
int main()
{
  long long x1, y1, x2, y2, u, l;
  bool num1 = 1;
  while (scanf("%d", &n), n)
  {
    scanf("%d%lld%lld%lld%lld", &m, &x1, &y1, &x2, &y2);
    a[0].x = x1, a[0].y = y1;
    b[0].x = x1, b[0].y = y2; // 左边界
    for (int i = 1; i <= n; i++)
    {
      scanf("%lld%lld", &u, &l);
      a[i].x = u, a[i].y = y1;
      b[i].x = l, b[i].y = y2; // 纸板端点
    }
    memset(ans, 0, sizeof ans);
    while (m--)
    {
      scanf("%lld%lld", &p.x, &p.y); // 玩具坐标
      ans[find(p)]++;                // 二分答案
    }
    num1 ? num1 = 0 : puts(""); // 第一行不输出空行
    for (int i = 0; i <= n; i++)
      printf("%d: %d\n", i, ans[i]);
  }
  return 0;
}