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;
}