求助 用乘法避免浮点数精度误差 sub1全wa

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
#define int long long
#define ll long long

struct Line
{
    int x0,x1,y0,y1;
    double k,b;
}line[maxn];
int tot;

int tree[maxn<<2];

bool check(int id1,int id2,int x)
{
    if(id1==0)return 0;
    if(id2==0)return 1;
    int x0=line[id1].x0,x1=line[id1].x1,y0=line[id1].y0,y1=line[id1].y1;
    int x2=line[id2].x0,x3=line[id2].x1,y2=line[id2].y0,y3=line[id2].y1;
    if(x0==x1||x2==x3)
    {
        long double ans1,ans2;
        ans1=(x0==x1?max(y0,y1):((long double)(y1-y0)/(x1-x0)*(x-x0)+y0));
        ans2=(x2==x3?max(y2,y3):((long double)(y3-y2)/(x3-x2)*(x-x2)+y2));
        if(fabs(ans1-ans2)<1e-12)return id1<id2;
        return ans1>ans2;
    }
    int fg=1LL*(x1-x0)*(x3-x2)>0;
    if(fg==0)fg=-1;
    __int128 flag=(__int128)(y1-y0)*(x-x0)*(x3-x2)+(__int128)y0*(x3-x2)*(x1-x0)-(__int128)(y3-y2)*(x-x2)*(x1-x0)-(__int128)y3*(x1-x0)*(x3-x2);
    return flag==0?(id1<id2):(flag*fg>0);
}

void update(int u,int l,int r,int l2,int r2,int id)
{
    if(l2>r||r2<l)return;
    int mid=l+r>>1;
    if(l2<=l&&r2>=r)
    {
        if(check(id,tree[u],mid))swap(id,tree[u]);
        if(l==r)return;
        if(check(id,tree[u],l))update(u<<1,l,mid,l2,r2,id);
        if(check(id,tree[u],r))update(u<<1|1,mid+1,r,l2,r2,id);
        return;
    }
    update(u<<1,l,mid,l2,r2,id);
    update(u<<1|1,mid+1,r,l2,r2,id);
}

int qry(int u,int l,int r,int pos)
{
    if(l==r)return tree[u];
    int mid=l+r>>1;
    int qr;
    if(pos<=mid)qr=qry(u<<1,l,mid,pos);
    else qr=qry(u<<1|1,mid+1,r,pos);
    if(check(tree[u],qr,pos))return tree[u];
    else return qr;
}

void solve()
{
    int n;cin>>n;
    int lst=0;
    for(int i=1;i<=n;i++)
    {
        int op;cin>>op;
        if(op==1)
        {
            int x0,y0,x1,y1;cin>>x0>>y0>>x1>>y1;
            x0=(x0+lst-1)%39989+1;
            y0=(y0+lst-1)%(1000000000)+1;
            x1=(x1+lst-1)%39989+1;
            y1=(y1+lst-1)%(1000000000)+1;
            //cout<<"x0 y0 x1 y1="<<x0<<' '<<y0<<' '<<x1<<' '<<y1<<'\n';
            line[++tot]={x0,x1,y0,y1};
            update(1,1,40000,min(x0,x1),max(x0,x1),tot);
        }
        else
        {
            int k;cin>>k;
            k=(k+lst-1)%39989+1;
            int ans=qry(1,1,40000,k);
            cout<<ans<<'\n';
            lst=ans;
        }

    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}