【ACWing】2983. 玩具

题目地址：

https://www.acwing.com/problem/content/description/2986/

计算玩具收纳盒中，每个分区内的玩具数量。约翰的父母有一个烦恼----约翰每次玩完玩具以后总会将玩具乱扔。他们为约翰准备了一个长方形的玩具收纳盒，用来放他的玩具。但是约翰非常调皮，每次都非常随意的将玩具扔进盒子中，使得所有玩具都随意混在一起，这让约翰难以找到他喜欢的玩具。对此，约翰的父母想出了一个对策，用若干个纸板将收纳盒分隔成若干个分区，这样至少扔到不同分区的玩具之间还是能分开的。下面是一个收纳盒的俯视图示例。

你的任务是，每当约翰将玩具扔进收纳盒中时，确定每个分区中有多少个玩具。

输入格式：
本题包含多组测试数据。
对于每组数据，第一行包含$6$个整数$n,m,x_1,y_1,x_2,y_2$，表示共有$n$个纸板，$m$个玩具，收纳盒的左上角坐标为$(x_1,y_1)$，右下角坐标为$(x_2,y_2)$。
接下来$n$行，每行包含两个整数$U_i,L_i$，表示第$i$个纸板的两端点坐标分别为$(U_i,y_1)$和$(L_i,y_2)$。数据保证纸板之间不相交，且按照从左至右顺序依次给出。
接下来$m$行，每行包含两个整数$X_j,Y_j$，表示第$j$个玩具的位置坐标。玩具的给出顺序是随机的。数据保证玩具不会恰好落在纸板上，也不会落在盒子外。
输入由包含单个$0$的一行结束。

输出格式：
对于每组数据，输出$n+1$行。
$n$个纸板将收纳盒划分为了$n+1$个分区，从左到右编号为$0\sim n$。
按照分区编号从小到大的顺序，每行输出一行信息$i:j$，其中$i$表示分区编号，$j$表示分区内玩具数量。
每组数据之间，用空行隔开。

数据范围：
每个测试点最多包含$10$组数据。
$1\le n,m\le 5000$
所有坐标取值范围$[-10^5,10^5]$。

对于某个玩具$(X_i,Y_i)$，和某个隔板$(U_i,y_1)-(L_i,y_2)$，它在隔板左边当且仅当$$\begin{gathered} ((U_i,y_1)-(L_i,y_2))\times ((X_i,Y_i)-(L_i,y_2))= \\ (U_i-L_i,y_1-y_2)\times (X_i-L_i,Y_i-y_2) \end{gathered}$$成右手系。由于隔板是从左到右给出的，所以某个玩具一定对于这些隔板依次是右右……左左……，从而可以二分出位置。代码如下：

#include <iostream>
#include <cstring>
#define x first
#define y second
using namespace std;
using PLL = pair<long, long>;

const int N = 5010;
int n, m;
PLL a[N], b[N];
int res[N];

PLL operator-(PLL a, PLL b) {
    
  return {
    a.x - b.x, a.y - b.y};
}

long cross(PLL a, PLL b) {
    
  return a.x * b.y - a.y * b.x;
}

int find(long x, long y) {
    
  int l = 0, r = n;
  while (l < r) {
    
    int mid = l + r >> 1;
    if (cross(a[mid] - b[mid], PLL{
    x, y} - b[mid]) > 0) r = mid;
    else l = mid + 1;
  }

  return l;
}

int main() {
    
  bool is_first = true;
  while (scanf("%d", &n), n) {
    
    long x1, y1, x2, y2;
    scanf("%d%ld%ld%ld%ld", &m, &x1, &y1, &x2, &y2);
    for (int i = 0; i < n; i++) {
    
      long u, l;
      scanf("%ld%ld", &u, &l);
      a[i] = {
    u, y1}, b[i] = {
    l, y2};
    }
    a[n] = {
    x2, y1}, b[n] = {
    x2, y2};

    if (is_first) is_first = false;
    else puts("");

    memset(res, 0, sizeof res);
    while (m--) {
    
      long x, y;
      scanf("%ld%ld", &x, &y);
      res[find(x, y)]++;
    }
    
    for (int i = 0; i <= n; i++)
      printf("%d: %d\n", i, res[i]);
  }
}

对于每组数据，时间复杂度$O(n+m\log n)$，空间$O(n)$。