[acwing] 2983. Toys

Title address ：

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

Calculate the toy storage box , Number of toys in each zone . John's parents have a problem ---- Every time John finishes playing with toys, he always throws them everywhere . They prepared a rectangular toy storage box for John , For his toys . But John is very naughty , Throw the toy into the box very casually every time , Make all toys mix together at will , This makes it difficult for John to find his favorite toy . Regarding this , John's parents came up with a countermeasure , Separate the storage box into several partitions with several cardboard , In this way, at least toys thrown into different zones can be separated . The following is a top view example of a storage box .

Your task is , Whenever John throws toys into the storage box , Determine how many toys are in each zone .

Input format ：
This question contains several groups of test data .
For each set of data , The first line contains $6$ It's an integer $n,m,x_1,y_1,x_2,y_2$, Expressing common ownership $n$ Cardboard ,$m$ A toy , The coordinate of the upper left corner of the storage box is $(x_1,y_1)$, The coordinates in the lower right corner are $(x_2,y_2)$.
Next $n$ That's ok , Each line contains two integers $U_i,L_i$, It means the first one $i$ The coordinates of the two ends of the cardboard are $(U_i,y_1)$ and $(L_i,y_2)$. The data ensures that the cardboard does not intersect , And in order from left to right .
Next $m$ That's ok , Each line contains two integers $X_j,Y_j$, It means the first one $j$ Position coordinates of toys . The order of toys is random . The data guarantees that the toy will not fall on the cardboard , Nor will it fall outside the box .
The input consists of a single $0$ End of line .

Output format ：
For each set of data , Output $n+1$ That's ok .
$n$ A cardboard divides the storage box into $n+1$ Zones , It's numbered... From left to right $0\sim n$.
In the order of division number from small to large , Output one line of information per line $i:j$, among $i$ Indicates the partition number ,$j$ Indicates the number of toys in the zone .
Between each group of data , Separate with blank lines .

Data range ：
Each test point can contain at most $10$ Group data .
$1\le n,m\le 5000$
All coordinate value ranges $[-10^5,10^5]$.

For a toy $(X_i,Y_i)$, And some partition $(U_i,y_1)-(L_i,y_2)$, It is on the left side of the partition if and only if $$\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}$$ Become a right-handed system . Because the clapboard is given from left to right , So a toy must be right for these partitions in turn …… Left, left ……, Thus, the position can be divided in two . The code is as follows ：

#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]);
  }
}

For each set of data , Time complexity $O(n+m\log n)$, Space $O(n)$.