要求在平面直角坐标系下维护两个操作： 
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。 
2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。

第一行一个整数n，表示共n 个操作。 
接下来n行，每行第一个数为0或1。 
 
若该数为 0，则后面跟着一个正整数 k，表示询问与直线  
x = ((k +lastans–1)%39989+1)相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中%表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段y坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号。 
若该数为 1，则后面跟着四个正整数 x0, y0, x 1, y 1，表示插入一条两个端点为 
((x0+lastans-1)%39989+1,(y0+lastans-1)%10^9+1)和((x
1+lastans-1)%39989+1,(y1+lastans-1)%10^9+1) 的线段。 
其中lastans为上一次询问的答案。初始时lastans=0。

对于每个 0操作，输出一行，包含一个正整数，表示交点最靠上的线段的编号。若不存在与直线相交的线段，答案为0。

对于100%的数据，1 ≤ n ≤ 10^5 , 1 ≤  k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。

 #include <bits/stdc++.h>

 struct line

 {

     int lt, rt;

     double k, b;

     line(void) {};

     line(int x0, int y0, int x1, int y1)

     {

         if (x0 < x1)

             lt = x0, rt = x1;

         else

             lt = x1, rt = x0;

         if (x0 == x1)

         {

             k = 0.0;

             b = y0 > y1 ? y0 : y1;

         }

         else

         {

             k = 1.0 * (y0 - y1) / (x0 - x1);

             b = y0 - x0 * k;

         }

     }

     inline double f(int x)

     {

         return k * x + b;

     }

 }ln[]; int tot;

 int sg(double x)

 {

     static const double eps = 1e-;

     return (x > -eps) - (x < +eps);

 }

 int cross(int i, int j)

 {

     return floor((ln[i].b - ln[j].b) / (ln[j].k - ln[i].k));

 }

 int flg[];

 int wi[]; double wy[];

 inline void update(int x, int p)

 {

     double y = ln[p].f(x);

     int s = sg(y - wy[x]);

     if (!wi[x] || s >  || (!s && p < wi[x]))

         wi[x] = p, wy[x] = y;

 }

 void insert(int t, int l, int r, int p)

 {

     if (ln[p].lt <= l && ln[p].rt >= r)

     {

         if (!flg[t])flg[t] = p;

         else

         {

             int mid = (l + r) >> ;

             bool lu = sg(ln[p].f(l) - ln[flg[t]].f(l)) > ;

             bool ru = sg(ln[p].f(r) - ln[flg[t]].f(r)) > ;

             if (lu && ru)flg[t] = p;

             else if (lu || ru)

             {

                 int tt = cross(p, flg[t]);

                 if (tt <= mid)

                 {

                     if (lu)

                         insert(t << , l, mid, p);

                     else

                         insert(t << , l, mid, flg[t]), flg[t] = p;

                 }

                 else

                 {

                     if (ru)

                         insert(t <<  | , mid + , r, p);

                     else

                         insert(t <<  | , mid + , r, flg[t]), flg[t] = p;

                 }

             }

             else

             {

                 update(l, p);

                 update(r, p);

             }

         }

     }

     else

     {

         int mid = (l + r) >> ;

         if (ln[p].lt <= mid)

             insert(t << , l, mid, p);

         if (ln[p].rt > mid)

             insert(t <<  | , mid + , r, p);

     }

 }

 int ansi; double ansy;

 void query(int t, int l, int r, int x)

 {

     if (flg[t])

     {

         double y = ln[flg[t]].f(x);

         int s = sg(y - ansy);

         if (s >  || (!s && flg[t] < ansi))

             ansi = flg[t], ansy = y;

     }

     if (l != r)

     {

         int mid = (l + r) >> ;

         if (x <= mid)

             query(t << , l, mid, x);

         if (x > mid)

             query(t <<  | , mid + , r, x);

     }

 }

 signed main(void)

 {

     int n; scanf("%d", &n);

     for (int ans = ; n--; )

     {

         int op; scanf("%d", &op);

         if (op)    // insert segment

         {

             int x0, y0, x1, y1;

             scanf("%d%d%d%d", &x0, &y0, &x1, &y1);

             x0 = (x0 + ans - ) %  + ;

             x1 = (x1 + ans - ) %  + ;

             y0 = (y0 + ans - ) %  + ;

             y1 = (y1 + ans - ) %  + ;

             ln[++tot] = line(x0, y0, x1, y1);

             insert(, , , tot);

         }

         else    // query segment

         {

             int x; scanf("%d", &x);

             x = (x + ans - ) %  + ;

             ansi = wi[x], ansy = wy[x];

             query(, , , x);

             printf("%d\n", ans = ansi);

         }

     }

 }