BZOJ 1390 Fence

发表于 | 更新于

Link

Solution

好题！ 首先，围栏的凸包之外的树一定是圈不到的，就不管它们，把答案加上。 而凸包里面的是一定要圈的，因为要圈一个最多得多建立3个栏杆，建栏杆的花费肯定比舍弃树的代价小。 然而，圈凸包不一定是最优的，最优的一定是能圈起所有凸包内树的最小的环。 下一步转化就非常厉害了： 对于环上的任意一条边，一定满足凸包内的树都在它的同侧。 那就枚举每对围栏（有向，即pi,pjp_i,p_j需要枚举 和 ），用叉积判断是否所有的树都在它的左侧。如果是，就把pip_i到pjp_j连一条长度为11的边。 最后用扩展Floyd求最小环即可。

Tips

这个解法依然是通过观察答案性质得到的。

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
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
//Code by Lucida
#include<bits/stdc++.h>
//#define red(x) scanf("%d",&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;}
using std::sort;
using std::swap;
const int MAXN=100+10,INF=0x1f1f1f1f;
struct vec
{
	int x,y;
	vec(){}
	vec(int _x,int _y):x(_x),y(_y){}
	void operator +=(vec a){x+=a.x,y+=a.y;}
	void operator -=(vec a){x-=a.x,y-=a.y;}
};
typedef vec point;
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
int inner(vec a,vec b){return a.x*b.x+a.y*b.y;}
int outer(vec a,vec b){return a.x*b.y-a.y*b.x;}
bool cmp(point a,point b)
{
	if(outer(a,b)!=0)
		return outer(a,b)>0;
	return inner(a,a)<inner(b,b);
}
int Graham(point *p,int n,point *hull)
{
	int mi=1;
	for(int i=1;i<=n;i++)
		if(p[i].x<p[mi].x || (p[i].x==p[mi].x && p[i].y<p[mi].y)) mi=i;
	swap(p[1],p[mi]),p[0]=p[1];
	for(int i=1;i<=n;i++) p[i]-=p[0];
	sort(p+2,p+1+n,cmp);
	for(int i=1;i<=n;i++) p[i]+=p[0];
	p[n+1]=p[1];
	static point S[MAXN];int top=0;
	for(int i=1;i<=n+1;i++)
	{
		while(top>=2 && outer(p[i]-S[top],S[top]-S[top-1])>0) top--;//>=0
		S[++top]=p[i];
	}
	top--;for(int i=1;i<=top;i++) hull[i]=S[i];
	return top;
}
bool cover(point a,point b,point c){return outer(b-a,c-a)==0 && (inner(c-a,c-a)<inner(b-a,b-a));}
bool cover(point *p,int n,point a)
{
	int wn=0;
	#define suc(i) (i+1>n?1:i+1)
	for(int i=1;i<=n;i++)
	{
		if(cover(p[suc(i)],p[i],a)) 
			return 1;
		if(outer(p[suc(i)]-p[i],a-p[i])>0 && a.y>p[i].y && a.y<=p[suc(i)].y) 
			wn++;
		if(outer(p[suc(i)]-p[i],a-p[i])<0 && a.y>p[suc(i)].y && a.y<=p[i].y) 
			wn--;
	}
	#undef suc
	return wn!=0;
}
bool check(point a,point b,point *t,int n)
{
	for(int i=1;i<=n;i++)
		if(outer(b-a,t[i]-a)<0) return 0;
	return 1;	
}
int main()
{
	static point p[MAXN],tr[MAXN],t[MAXN],hull[MAXN];
	//freopen("input","r",stdin);
	int n,m;red(n),red(m);
	for(int i=1;i<=n;i++)
		red(p[i].x),red(p[i].y);
	for(int i=1;i<=m;i++)
		red(tr[i].x),red(tr[i].y);
	int hc=Graham(p,n,hull);
	int tc=0,ANS=0;
	for(int i=1;i<=m;i++)
		if(cover(hull,hc,tr[i]))
			t[++tc]=tr[i];
		else
			ANS+=111;
	if(tc)
	{
		static int sp[MAXN][MAXN],dist[MAXN][MAXN];
		memset(sp,31,sizeof(sp));
		for(int i=1;i<=n;i++)//有向。。。
			for(int j=1;j<=n;j++)
				if(i!=j && check(p[i],p[j],t,tc))
					sp[i][j]=1;
		for(int i=1;i<=n;i++) sp[i][i]=0;
		memcpy(dist,sp,sizeof(sp));
		int res=INF;
		for(int k=1;k<=n;k++)
		{
			for(int i=1;i<k;i++)
				for(int j=i+1;j<k;j++)
					chkmn(res,sp[i][j]+dist[j][k]+dist[k][i]);
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					chkmn(sp[i][j],sp[i][k]+sp[k][j]);
		}
		ANS+=res*20;
	}
	printf("%d\n",ANS);
	return 0;
}