3165: [Heoi2013]Segment
Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 465 Solved: 187
[Submit][Status][Discuss]
Description
要求在平面直角坐标系下维护两个操作：
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。
2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。
Input
第一行一个整数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。
Output
对于每个 0操作，输出一行，包含一个正整数，表示交点最靠上的线段的编号。若不存在与直线相交的线段，答案为0。
Sample Input
6
1 8 5 10 8
1 6 7 2 6
0 2
0 9
1 4 7 6 7
0 5
1 8 5 10 8
1 6 7 2 6
0 2
0 9
1 4 7 6 7
0 5
Sample Output
2
0 3
0 3
HINT
对于100%的数据，1 ≤ n ≤ 10^5 , 1 ≤ k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。
Source
线段树维护线段，23333
#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);
}
}
}
@Author: YouSiki