22 Grab the Seat 1 C.Grab the Seat (Geometry + Violence)

Portal

The gist of the title: A two-dimensional plane has a screen from 1 to m on the y-axis, the plane class has a matrix from (1,1) to (n,m), and the matrix hask seats are already seated, q times of inquiries, each time modifying the coordinates of one person, to find a seat where the screen line of sight is not blocked

Thinking: For the case of y = 1 and m, it will only block the person behind it, i.e. to the right of the x coordinate, and a special judgment can be made

In general, it can be regarded as two rays from (0, 1), (0, m) to this point, the range behind the rays is the blocking range, and the left boundary of the entire area can be regarded as a line graph, just calculate the abscissa of each line of the line chart, we can calculate separately

Looking at the ray from (0, 1) first, the red area is the occluded area. It can be found that the point with a small slope below will be covered. Because it is a point below, the slope must be less than, andIt is not difficult to observe that the slope is monotonic

Similarly from (0, m), just reverse it, the final answer is actually the union of the two, that is, the minimum value can be updated each time

The code is as follows:

#include using namespace std;stringstream ss;#define endl "\n"typedef long long ll;typedef pair PII;typedef pair, int> PIII;const int N = 2e5+10, M = 30, mod = 1e9+7;const int INF = 0x3f3f3f3f;int n,m,k,q;ll x[N], y[N]; // x, y record the coordinates of each numberll x1[N], minx[N]; // x1 records the leftmost abscissa of each line (the greatest impact), minx records the impactvoid solve(){cin>>n>>m>>k>>q;for(int i = 1; i<=k; i++) cin>>x[i]>>y[i];while(q -- ){int id;cin>>id;cin>>x[id]>>y[id];for(int i = 0; i my/mx update slope if current slope is greaterll cx = x1[i], cy = i;if(cy*mx > cx*my) mx = cx, my = cy;ll res;if(my) res = ceil(mx*i*1.0 / my) - 1; // Calculate the abscissa of the intersection -1 means that the intersection may also be blockedelse res = n; // The first line does not need to be calculated, and it is directly judged to only affect the following peopleminx[i] = min(res, minx[i]);}// Invert the ray of (0, m) calculated according to the (0, 0) ray codereverse(x1, x1+m);mx = n+1, my = 0;for(int i = 0; i cx*my) mx = cx, my = cy;ll res;if(my) res = ceil(mx*i*1.0 / my) - 1;else res = n;minx[m - i - 1] = min(res, minx[m - i - 1]);}ll ans = 0;for(int i = 0; i>T;// while(T -- )// {// solve();// }}