[题解] [HNOI2008]水平可见直线-bzoj1007

oi
  1. 1. 水平可见直线-bzoj1007

水平可见直线-bzoj1007


没写单调栈

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <bits/stdc++.h>

using namespace std;

namespace CG
{
template<typename T>
inline T abs(T val) { return val < 0 ? -val : val; }

const double eps = 1e-8;

class Point
{
public:
double x, y;
Point() {}
Point(double a, double b): x(a), y(b)
{}
Point operator+ (const Point &a) { return Point(x + a.x, y + a.y); }
Point operator- (const Point &a) { return Point(x - a.x, y - a.y); }
Point operator* (const double &a) { return Point(x * a, y * a); }
Point operator/ (const double &a) { return Point(x / a, y / a); }
Point operator= (const Point &a) { x = a.x, y = a.y; return Point(x, y); }
double operator* (const Point &a) { return x * a.y - y * a.x; }
bool operator< (const Point &a)
{ return fabs(x - a.x) < eps ? y > a.y : x > a.x; }
bool operator== (const Point &a)
{ return fabs(x - a.x) < eps && fabs(y - a.y) < eps; }
};

class Segments
{
public:
double a, b;
int index;
Segments() {}
Segments(double x, double y): a(x), b(y)
{}
Segments(double x, double y, int i): a(x), b(y), index(i)
{}
Segments operator= (const Segments &x)
{ a = x.a, b = x.b, index = x.index; return Segments(x.a, x.b); }
bool operator== (const Segments &x)
{ return fabs(a - x.a) < eps && fabs(b - x.b) < eps; }
bool operator< (const Segments &x)
{ return fabs(a - x.a) < eps ? b < x.b : a < x.a; }
};

std::ostream &operator<<(std::ostream &os, const Point &p)
{
os << "(" << p.x << ", " << p.y << ")";
return os;
}

std::ostream &operator<<(std::ostream &os, const Segments &p)
{
os << "(" << p.a << ", " << p.b << ")";
return os;
}

inline Point inter(Segments x, Segments y)
{
double rex = (double)(x.b - y.b) / (double)(y.a - x.a);
double rey = x.a * rex + x.b;
return Point(rex, rey);
}
}

namespace solve
{
using namespace CG;

inline int read()
{
char c = getchar();
int ret = 0, f = 1;
for (; !isdigit(c); f = c == '-' ? -1 : 1, c = getchar());
for (; isdigit(c); ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

double n, a, b;
vector<Segments> sg;
vector<int> res;
bitset<50005> used;
double maxx = -1e9;

template<typename T>
inline bool eql(T a, T b) {
return fabs(a - b) < eps;
}

inline Segments the_next(Segments curr)
{
// 鑾峰彇鑳藉璧板埌鐨勪笅涓€涓?
double minx, mina, minb;
int minindex = 0;
minx = mina = minb = 1e9;
for (int i = 0; i < sg.size(); ++i)
{
if(!used[sg[i].index] && !eql(curr.a, sg[i].a)) {
Point ret = inter(curr, sg[i]);
if(ret.x <= maxx) continue;
if(eql(ret.x, minx)) {
if (sg[i].a > mina)
mina = sg[i].a, minindex = i;
} else if (ret.x < minx) {
minx = ret.x, minindex = i;
}
}
} // 鑾峰彇y鏈€澶х殑閭d釜鐐瑰拰鎵€鏈夌洿绾裤€?
used[sg[minindex].index] = true;
maxx = max(maxx, minx);
return sg[minindex];
}

inline void init()
{
n = read();
for (register int i = 1; i <= n; ++i)
{
a = read(); b = read();
sg.push_back(Segments(a, b, i));
}
}
/*
涓や釜O(n)姹傚嚭鏈€宸﹁竟鐨勭鐐癸紝
*/
inline void solve()
{
init();
Segments seg_min(1e9, 1e9); // 鏈€灏廰鐨勭嚎娈?
Segments seg_max(-1e9, -1e9); // 鏈€澶鐨勭嚎娈?
for (int i = 0; i < sg.size(); ++i)
{
if(eql(seg_min.a, sg[i].a)) {
if(seg_min.b < sg[i].b)
seg_min = sg[i];
} else if(seg_min.a > sg[i].a) {
seg_min = sg[i];
}
if(eql(seg_max.a, sg[i].a)) {
if(seg_max.b < sg[i].b)
seg_max = sg[i];
}
else if(seg_max.a < sg[i].a) {
seg_max = sg[i];
}
}
// seg_min鏄枩鐜囨渶澶х殑绾挎
res.push_back(seg_min.index);
used[seg_min.index] = true;
while(!(seg_max == (seg_min = the_next(seg_min)))) res.push_back(seg_min.index);
res.push_back(seg_max.index);
used[seg_max.index] = true;
sort(res.begin(), res.end());
for (int i = 0; i < res.size(); ++i) cout << res[i] << " ";
}
}

int main()
{
solve::solve();
}

嘛只是想到了一个比较骚的方法
算了不说了,调了三个小时,说多了全是泪
思路有点不一样
别人用单调栈,我下楼吃午饭的时候脑洞到了一个方法,给lr说了一下,然后就开始写。写了150lines(单调栈解法40lines
简述一下方法吧…
我利用了一个可能的性质
我们需要随时把点维护在最上方,所以就利用一个贪心的性质。每走一步。选取距离x最近的前提下,与其相交的线段的a最大,的交点。然后走上这条线段。理论复杂度$O(n^2)$,虽然是$n^2$,但是实际为$O(nm)$,$m=输出的个数$
啊啊啊不说了累死了回家了

这份题解存在的意义是“提供另一种”解题思路

这个算法的时间复杂度以及怎么卡lr给出了qwq, 具体在这里