模板P4097 不判点相等时编号大小评测结果

判点相等时编号大小这里

玄关求调

#include<bits/stdc++.h>
using namespace std;
const int mod=39989,mod2=1e9+1;
const double eps=1e-9;
int T,lans,op,x0,yo,x1,yl,cnt,ls;
struct ss
{
	double k,b;
	int l,r;
}ed[100005];
void add()
{
	cnt++;
	if(x0==x1)
	{
		ed[cnt].l=ed[cnt].r=x0;
		ed[cnt].k=0;
		ed[cnt].b=max(yo,yl);
	}
	ed[cnt].l=x0;
	ed[cnt].r=x1;
	ed[cnt].k=(double)(yl-yo)*1.000/(double)(x1-x0);
	ed[cnt].b=yo*1.000-x0*ed[cnt].k;
}
struct sd
{
	int l,r;
	int sid;
}tr[300005];
double cacl(int id,int pos)
{
	return ed[id].k*pos+ed[id].b;
}
int cmp(double aa,double bb)
{
	if(aa-bb>=eps) return 1;
	if(bb-aa>=eps) return -1;
	return 0;
}
void upd(int pos,int id)
{
	ls=(tr[pos].l+tr[pos].r)/2;
	double mid=ls;
	if(tr[pos].sid==0) 
	{
		tr[pos].sid=id;
		return ;
	}
	int fl=cmp(cacl(id,mid),cacl(tr[pos].sid,mid));
	if(fl==1||(fl==0&&id<tr[pos].sid))
	{
		swap(id,tr[pos].sid);
	}
	if(tr[pos].l==tr[pos].r) return ;
	fl=cmp(cacl(id,tr[pos].l),cacl(tr[pos].sid,tr[pos].l));
	if(fl==1||(fl==0&&id<tr[pos].sid))
	{
		upd(pos*2,id);
		return ;
	}
	fl=cmp(cacl(id,tr[pos].r),cacl(tr[pos].sid,tr[pos].r));
	if(fl==1||(fl==0&&id<tr[pos].sid))
	{
		upd(pos*2+1,id);
		return ;
	}
	return ;
}
void update(int pos,int l,int r,int id)
{
	if(tr[pos].r<l||tr[pos].l>r) return ;
	if(tr[pos].l>=l&&tr[pos].r<=r)
	{
		upd(pos,id);
		return ;
	}
	update(pos*2,l,r,id);
	update(pos*2+1,l,r,id);
}
void build(int pos,int l,int r)
{
	tr[pos].l=l;
	tr[pos].r=r;
	if(l==r) return ;
	build(pos*2,l,(l+r)/2);
	build(pos*2+1,(l+r)/2+1,r);
}
void query(int id,int k)
{
	if(tr[id].l>k||tr[id].r<k) return ;
	int fl=cmp(cacl(tr[id].sid,k),cacl(lans,k));
	if(fl==1||(fl==0&&tr[id].sid<lans))
	{
		lans=tr[id].sid;
	}
	if(tr[id].l==tr[id].r) return ;
	query(id*2,k);
	query(id*2+1,k);
}
int main()
{
	build(1,1,mod);
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&op);
		if(op==0)
		{
			scanf("%d",&x0);
			x0=(x0+lans-1)%mod+1;
			lans=0;
			query(1,x0);
			printf("%d\n",lans);
		}
		else
		{
			scanf("%d%d%d%d",&x0,&yo,&x1,&yl);
			x0=(x0+lans-1)%mod+1;
			x1=(x1+lans-1)%mod+1;
			yo=(yo+lans-1)%mod2+1;
			yl=(yl+lans-1)%mod2+1;
			if(x0>x1) swap(x0,x1),swap(yo,yl);
			add();
			update(1,x0,x1,cnt);
		}
	}
	return 0;
}