1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include <cstdio>
#include <vector>
using namespace std;
typedef pair<double, int> PDI;
const int N = 39989;
const double inf = 1e18, eps = 1e-10;
int cmp(double a, double b)
{
if (a - b > eps)
return 1;
if (b - a > eps)
return -1;
return 0;
}
PDI Max(PDI a, PDI b)
{
if (!cmp(a.first, b.first))
return a.second > b.second ? a : b;
return a.first > b.first ? a : b;
}
struct Node
{
int l, r, v;
} tr[N << 2];
struct Line
{
double k, b;
};
vector<Line> p;
void add(int x0, int y0, int x1, int y1)
{
if (x0 == x1)
p.push_back((Line){0, max(y0, y1)});
else
p.push_back((Line){1.0 * (y1 - y0) / (x1 - x0), y0 - 1.0 * (y1 - y0) / (x1 - x0) * x0});
}
void build(int x, int l, int r)
{
tr[x].l = l, tr[x].r = r;
tr[x].v = -1;
if (l == r)
return;
int mid = l + r >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
}
double cal(int t, int x)
{
if (~t)
return p[t].k * x + p[t].b;
return -inf;
}
void modify(int x, int l, int r, int t)
{
int mid = tr[x].l + tr[x].r >> 1;
if (tr[x].l >= l && tr[x].r <= r)
{
if (cmp(cal(t, mid), cal(tr[x].v, mid)) > 0)
swap(t, tr[x].v);
if (cmp(cal(t, tr[x].l), cal(tr[x].v, tr[x].l)) > 0)
modify(x << 1, l, r, t);
if (cmp(cal(t, tr[x].r), cal(tr[x].v, tr[x].r)) > 0)
modify(x << 1 | 1, l, r, t);
return;
}
if (l <= mid)
modify(x << 1, l, r, t);
if (r > mid)
modify(x << 1 | 1, l, r, t);
}
PDI query(int x, int t)
{
PDI cur = (PDI){cal(tr[x].v, t), tr[x].v};
if (tr[x].l == tr[x].r)
return cur;
int mid = tr[x].l + tr[x].r >> 1;
return Max(cur, query(t <= mid ? x << 1 : x << 1 | 1, t));
}
int main()
{
build(1, 1, N);
int q;
scanf("%d", &q);
for (int op; q; q--)
{
scanf("%d", &op);
if (op == 0)
{
int x;
scanf("%d", &x);
printf("%d\n", query(1, x).second + 1);
}
else if (op == 1)
{
int x0, y0, x1, y1;
scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
x0 > x1 && (swap(x0, x1), swap(y0, y1), 0);
add(x0, y0, x1, y1);
modify(1, x0, x1, p.size() - 1);
}
}
return 0;
}
|