HDU 4946 Area of Mushroom （凸包）

发表于 |
字数统计: 1,058字 | 阅读时长 ≈ 5min

Area of Mushroom

问题描述

**中学有一个很大的操场，上面有n名同学(编号1到n)。我们可以看做一个无限大的平面上有n个坐标点。同学们跑步速度有快有慢。对于操场上的任何一点，如果一个学生能比其他学生都先到达(跑直线，没有人比他先到或同时到)，那么这个点就被他占领。 请你计算，哪些同学能占领无穷多个点。

输入格式

输入含有多组数据(<=8组)，对于每组数据：
第一行一个整数n。

接下来n行，每行三个整数x,y,v，按1到n的顺序依次描述一个同学的位置坐标(x,y)和他的跑步速度。

输入以单独一行，一个数字0作为结束。

输出格式

对于每组数据，输出一行，n个数字，对应1到n号学生的情况。如果该学生能占用无限多个点，输出1，否则输出0。

样例输入 1

3
0 0 3
1 1 2
2 2 1
0

样例输出 1

100

样例输入 2

3
0 0 2
1 1 1
2 0 2
4
1 1 3
1 1 2
2 2 2
3 3 1
0

样例输出 2

101
1000

提示

对于20%的数据： 1<=n<=5
对于100%的数据：1<=n<=500 0<=|x|,|y|,v<=10^4

首先注意到只有速度最大的人才有可能占有无限的面积，这个比较显然，推式子的话会发现如果速度不相等，那么最终速度小的占有的会是一个圆。

因此只考虑速度最大的人，那么只有凸包上的人才能占有无限的面积，这个也比较容易脑补。因此只需要求出所有速度最大的人的凸包。

但是注意到两种特殊情况。
一是如果所有人速度都为0，那么答案显然都为0。
二是可能存在两个人的坐标相同，速度也相同，此时根据题意，两个人占有的面积都是0，需要特判，但是注意求凸包的时候，所有坐标速度都相同的人只能加一个且必须加一个，加多了会导致求凸包算法出问题，因为本题中凸包上三点共线是要保留的，因此有重点就会使得该被弹掉的点弹不掉。

复杂度$O(n\log n)$，事实上是可以推导一番用半平面交的，但精度好像有点问题？

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1005
using namespace std;
const double eps=1e-12;
struct node{double x,y;int id;}P[N],T[N],S[N];
bool operator<(node a,node b)
{
	if(a.x==b.x)return a.y>b.y;
	return a.x<b.x;
}
node operator-(node a,node b){return (node){a.x-b.x,a.y-b.y};}
double operator*(node a,node b){return a.x*b.y-a.y*b.x;}
int n,v[N],top,m,tot;
bool mark[N],rem[N];
bool find(int x)
{
	bool f=0;
	for(int i=1;i<=n;i++)
	{
		if(i==x)continue;
		if(P[i].x!=P[x].x)continue;
		if(P[i].y!=P[x].y)continue;
		if(v[i]!=v[x])continue;
		f=1;rem[i]=1;
	}
	return f;
}
bool judge(node a,node b,node c)
{return (b-a)*(c-a)<0;}
void GetTB()
{
	int i,j,k;top=0;
	sort(T+1,T+tot+1);
	for(i=1;i<=tot;i++)
	{
		while(top>1&&judge(S[top-1],S[top],T[i]))top--;
		S[++top]=T[i];
	}
	k=--top;
	for(i=tot;i>=1;i--)
	{
		while(top>k+1&&judge(S[top-1],S[top],T[i]))top--;
		S[++top]=T[i];
	}
	for(i=1;i<=top;i++)mark[S[i].id]=1;
}
int main()
{
	int i,j,k,Max;
	while(scanf("%d",&n))
	{
		if(n==0)break;Max=0;tot=0;
		memset(mark,0,sizeof(mark));
		memset(rem,0,sizeof(rem));
		for(i=1;i<=n;i++)scanf("%lf%lf%d",&P[i].x,&P[i].y,&v[i]);
		for(i=1;i<=n;i++)Max=max(Max,v[i]),P[i].id=i;
		if(Max==0)
		{
			for(i=1;i<=n;i++)putchar('0');
			puts("");continue;
		}
		for(i=1;i<=n;i++)if(v[i]==Max&&!rem[i])T[++tot]=P[i],find(i);
		GetTB();
		for(i=1;i<=n;i++)mark[i]&&!find(i)?putchar('1'):putchar('0');
		puts("");
	}
}