[noi simulation] computational geometry (convex hull, violence, and search set)

Topic

One sentence question ： On a given plane $n$ On the hour , Multiply the area of convex hull 2 Value .

Data generation ：

Given $x_0,y_0,a_x,a_y,b_x,b_y,p_x,p_y,n$ ,
$$\begin{gathered} x_i=(a_x{x}_{i-1}+b_x)\mathrm{mod}{p}_x \\ {y}_i=(a_y{y}_{i-1}+b_y)\mathrm{mod}{p}_y \end{gathered}$$

Finally get $n$ A little bit $(x_0,y_0),(x_1,y_1),...,(x_{n-1},y_{n-1})$ .

n ≤ 10¹⁸

p_x,p_y ≤ 200000

Answer key

We found this n Particularly large , But the coordinate range is relatively small .

I believe everyone who has done plane convex hull has such a dream ： Calculate the minimum and maximum vertical coordinates corresponding to each value of the abscissa , Do slope optimization as two sequences to find convex hull . But the helplessness range is usually very large , This idea usually doesn't work .

This problem is different , As for the relatively small , We can find the minimum ordinate and maximum ordinate corresponding to each abscissa .

According to the pigeon cage principle ,n When it is very large, the abscissa and ordinate must form a cycle .

We find the moment when each ordinate first appears （ So to speak ） And the second moment （ If any ）, And then grow up / Enumerate ordinates from large to small and assign values to abscissa . Because it is not difficult to find that it will only form a cycle , So the difference between the second moment and the first moment of each position is equal .

We enumerate the corresponding abscissa for each ordinate , Violence assignment , You need to skip the abscissa that has been assigned . Because no matter what the ordinate is , The next abscissa of the same ordinate depends only on the current abscissa , So we can use the union search set to maintain the assigned continuous segments , Make sure you can $O(\log p)$ skip .

Time complexity $O(p\log p)$ .

CODE

// ubsan: undefined
// accoders
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN 200005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
#define SQ 317
int xchar() {
    
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
    
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {
    if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {
    x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {
    if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {
    putnum(x);putchar(c);}

int n,m,s,o,k;
int l[MAXN],r[MAXN];
int P = 1;
struct it{
    
	int a,b;LL c;
	it(){
    a=1;b=0;c=0;}
	it(int A,int B,LL C){
    a=A;b=B;c=C;}
}kx[MAXN],ky[MAXN];
inline it operator * (it l,it r) {
    
	l.a = l.a*1ll*r.a % P;
	l.b = (l.b*1ll*r.a + r.b) % P;
	l.c += r.c; return l;
}
inline int operator * (int x,it y) {
    
	return (x*1ll*y.a + y.b) % P;
}
PR fr[MAXN];
it la[MAXN];
int fa[MAXN];
it fe[MAXN];
int findf(int x) {
    
	if(x == fa[x]) return x;
	int r = fa[x],f = findf(r);
	fe[x] = fe[x]*fe[r]; fa[x] = f;
	return f;
}
void unionSet(int u,int f,it k) {
    
	fa[u] = findf(f); fe[u] = k*fe[f];
}
PR ar[MAXN<<1];
int ca;
int st[MAXN],tp;
LL S(PR a,PR b,PR c) {
    
	PR A = {
    a.FI-b.FI,a.SE-b.SE};
	PR B = {
    c.FI-b.FI,c.SE-b.SE};
	LL rs = A.SE*1ll*B.FI - A.FI*1ll*B.SE;
	return rs<0 ? -rs:rs;
}
int main() {
    
	freopen("geometry.in","r",stdin);
	freopen("geometry.out","w",stdout);
	int x0 = read(),y0 = read();
	int ax = read(),ay = read();
	int bx = read(),by = read();
	it tx = it(ax,bx,1),ty = it(ay,by,1);
	n = read();m = read();
	LL N = read();
	P = n;
	for(int i = 1;i < n;i ++) kx[i] = kx[i-1]*tx;
	P = m;
	for(int i = 1;i < m;i ++) ky[i] = ky[i-1]*ty;
	for(int i = 0;i < n;i ++) {
    
		l[i] = m+1; r[i] = -1;
		fa[i] = i; fe[i] = it();
	}
	P = m;
	int p = y0,ct = 0,xx = x0;
	while(!la[p].c && ct < N) {
    
		if(!fr[p].FI) {
    
			fr[p] = {
    ct+1,xx};
		}
		else if(!la[p].c) {
    
			la[p] = kx[ct-fr[p].FI+1];
		}
		p = p*ty; ct ++;
		P = n; xx = xx*tx; P = m;
	}
	P = n;
	for(int i = 0;i < m;i ++) {
    
		if(fr[i].FI) {
    
			int p = fr[i].SE;
			LL cn = fr[i].FI-1;
			findf(p); cn += fe[p].c;
			p = fa[p];
			while(cn < N) {
    
				l[p] = min(l[p],i);
				r[p] = max(r[p],i);
				if(!la[i].c) break;
				int nx = p*la[i];
				if(findf(nx) == p) break;
				unionSet(p,nx,la[i]);
				findf(p); cn += fe[p].c;
				p = fa[p];
			}
		}
	}
	for(int i = 0;i < n;i ++) fa[i] = i,fe[i] = it();
	for(int i = m-1;i >= 0;i --) {
    
		if(fr[i].FI) {
    
			int p = fr[i].SE;
			LL cn = fr[i].FI;
			findf(p); cn += fe[p].c;
			p = fa[p];
			while(cn <= N) {
    
				l[p] = min(l[p],i);
				r[p] = max(r[p],i);
				if(!la[i].c) break;
				int nx = p*la[i];
				if(findf(nx) == p) break;
				unionSet(p,nx,la[i]);
				findf(p); cn += fe[p].c;
				p = fa[p];
			}
		}
	}
	int ll = n-1,rr = 0;
	for(int i = 0;i < n;i ++) {
    
		if(l[i] < n && r[i] >= 0) {
    
			ll = min(ll,i); rr = max(rr,i);
		}
	}
	tp = 0;
	for(int i = ll;i <= rr;i ++) {
    
		if(l[i] >= n || r[i] < 0) continue;
		while(tp > 1 && (l[st[tp]]-l[st[tp-1]])*1ll*(i-st[tp]) >= (l[i]-l[st[tp]])*1ll*(st[tp]-st[tp-1])) {
    
			st[tp --] = 0;
		}
		st[++ tp] = i;
	}
	for(int i = 1;i <= tp;i ++) {
    
		ar[++ ca] = {
    st[i],l[st[i]]};
	}
	tp = 0;
	for(int i = ll;i <= rr;i ++) {
    
		if(l[i] >= n || r[i] < 0) continue;
		while(tp > 1 && (r[st[tp]]-r[st[tp-1]])*1ll*(i-st[tp]) <= (r[i]-r[st[tp]])*1ll*(st[tp]-st[tp-1])) {
    
			st[tp --] = 0;
		}
		st[++ tp] = i;
	}
	for(int i = tp;i > 0;i --) {
    
		ar[++ ca] = {
    st[i],r[st[i]]};
	}
	LL ans = 0;
	for(int i = 3;i <= ca;i ++) {
    
		ans += S(ar[1],ar[i-1],ar[i]);
	}
	AIput(ans,'\n');
	return 0;
}