BZOJ

半平面交（三弹连发）

半平面交基本概念

  • 半平面：由不等式ax+by+c>=0确定。
  • 在一个有界区域里半平面或半平面的交是一个凸多边形区域。
  • n个半平面的交是一个至多n条边的凸多边形。

    BZOJ 1007 水平可见直线

    题意

    平面直角坐标系上，有n条直线，从y为正无穷处往下看。问能看看到哪些直线？

    数据范围

    $$n\leq50000$$

    题解

    当一条直线不是最后半平面交的组成部分，仅当它被与它斜率相同的直线挡住，或被两条斜率不同的直线挡住。如图：

    斜率:l1< l2< l3；交点横坐标:x1< x2。l2不是半平面交的组成部分，仅当x1<=x2。
    即直线与比它斜率小的直线的交点，比与比它大的直线的交点横坐标大或等于。

    代码

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
#include<cstdio>
#include<algorithm>
using namespace std;
struct line
{
	int a,b,num;
	bool operator < (const line c) const
	{
		if (a==c.a) return b<c.b;
		return a<c.a;
	}
}l[50010];
int q[50010];
bool v[50010];
double calc(int x,int y)
{
	return double(l[y].b-l[x].b)/double(l[x].a-l[y].a);
}
int main()
{
	int n,num=0;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)	scanf("%d%d",&l[i].a,&l[i].b),l[i].num=i;
	sort(l+1,l+n+1);
	for (int i=1;i<=n;i++)
	{
		if(i<n&&l[i].a==l[i+1].a) continue;
		while(num>1&&calc(q[num],i)<=calc(q[num-1],i)) v[l[q[num]].num]=false,num--;
		q[++num]=i; v[l[i].num]=true;
	}
	for (int i=1;i<=n;i++)
	if (v[i]) printf("%d ",i);
	return 0;
}

BZOJ 3190 赛车

题意

n辆赛车，赛车gi起始位于距离起跑线前进ki的位置。比赛开始后以vi速度行驶，只要它在某一时刻位于最领先位置就能得奖。求能得奖的赛车。

题解

如果画出x-t图像就能发现，每辆赛车相当于一条直线，斜率为vi。求半平面交。（代码略）

BZOJ 1038 瞭望塔

题意

H村轮廓为(x1,y1),(x2,y2)…(xn,yn)连成的折线。满足x1< x2<…xn要求在某点建一个瞭望塔，满足在瞭望塔上能看到H村的任意位置。求瞭望塔的最小高度。

题解

将折线延长求半平面交中的最低点。那么瞭望塔所建的位置一定是最低点或H村轮廓的最高点。（正好是上凸壳的最低点或下凸壳的最高点）（代码略）