BZOJ1007 水平可见直线

Link

Solution

半平面交的弱化版。由于不需要去切割队首半平面,可以直接用一个栈。

Code

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
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=50000+10;
using std::sort;
typedef double ld;
ld eps=1e-7;
int fcmp(ld x)
{
if(-eps<x && x<eps) return 0;
return x<0?-1:1;
}
struct point
{
ld x,y;
point(){}
point(ld _x,ld _y):x(_x),y(_y){}
};
typedef point vec;
vec operator-(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
ld outer(vec a,vec b){return a.x*b.y-a.y*b.x;}
struct line
{
ld k,b;int id;
line(){}
line(ld _k,ld _b):k(_k),b(_b){}
bool operator <(const line &a)const
{
if(k!=a.k) return k<a.k;
return b>a.b;
}
};
bool cmp(const line &a,const line &b){return a.id<b.id;}
bool onleft(point a,line l){return fcmp(outer(a-point(0,l.b),vec(1,l.k)))<0;}
point cross(line a,line b)
{
point o;o.x=-(a.b-b.b)/(a.k-b.k);
o.y=a.k*o.x+a.b;
return o;
}
int main()
{
//freopen("input","r",stdin);
static line l[MAXN];
int n;red(n);
for(int i=1;i<=n;i++)
fred(l[i].k),fred(l[i].b),l[i].id=i;
sort(l+1,l+1+n);
static line S[MAXN];
int top=0;
for(int i=1;i<=n;i++)
{
if(fcmp(S[top].k-l[i].k)==0) continue;
while(top>1 && !onleft(cross(S[top-1],S[top]),l[i])) top--;
S[++top]=l[i];
}
sort(S+1,S+1+top,cmp);
for(int i=1;i<=top;i++) printf("%d ",S[i].id);
puts("");
return 0;
}

套模板

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
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=50000+1;
using std::sort;
typedef double ld;
ld eps=1e-7;
int fcmp(ld x)
{
if(-eps<x && x<eps) return 0;
return x<0?-1:1;
}
struct point
{
ld x,y;
point(){}
point(ld _x,ld _y):x(_x),y(_y){}
};
typedef point vec;
vec operator-(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
ld outer(vec a,vec b){return a.x*b.y-a.y*b.x;}
struct line
{
ld k,b;int id;
line(){}
line(ld _k,ld _b):k(_k),b(_b){}
bool operator <(const line &a)const
{
if(k!=a.k) return k<a.k;
return b<a.b;
}
};
bool cmp(const line &a,const line &b){return a.id<b.id;}
bool onleft(point a,line l){return fcmp(outer(a-point(0,l.b),vec(1,l.k)))<0;}
point cross(line a,line b)
{
point o;o.x=-(a.b-b.b)/(a.k-b.k);
o.y=a.k*o.x+a.b;
return o;
}
int main()
{
//freopen("input","r",stdin);
static line l[MAXN];
int n;red(n);
for(int i=1;i<=n;i++)
fred(l[i].k),fred(l[i].b),l[i].id=i;
sort(l+1,l+1+n);
static line Ql[MAXN];
static point Qp[MAXN];
int head,tail;
Ql[head=tail=1]=l[1];
#define count(x,y) (y-x+1)
for(int i=2;i<=n;i++)
{
while(count(head,tail)>=2 && !onleft(Qp[tail-1],l[i]))
tail--;
while(count(head,tail)>=2 && !onleft(Qp[head],l[i]))
head++;
Ql[++tail]=l[i];
if(fcmp(Ql[tail-1].k-Ql[tail].k)==0)
{
tail--;
if(fcmp(l[i].b-Ql[tail].b)>0)
Ql[tail]=l[i];
}
if(count(head,tail)>=2)
Qp[tail-1]=cross(Ql[tail-1],Ql[tail]);
}
while(count(head,tail)>=2 && !onleft(Qp[tail-1],Ql[head])) tail--;
#undef count
sort(Ql+head,Ql+tail+1,cmp);
for(int i=head;i<=tail;i++) printf("%d ",Ql[i].id);
puts("");
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利