crazy_cloud's Blog
0%

TopCoder SRM679 Division I Medium RedAndBluePoints

Posted on Edited on In

题目大意

二维平面上有 \(n\) 个蓝点和 \(m\) 个红点。你要画出一个凸多边形，使其在不包含任何红点的同时包含尽可能多的蓝点。请输出最多包含的蓝点数。

这个凸多边形可以退化成点或线段。

\(1\leq n,m\leq 50\)

坐标都是 \([0,10^3]\) 的整数，保证没有两点重叠和三点共线。

题目分析

和求凸包一样，我们先把所有点按照 \(x\) 坐标排序，然后将凸多边形分成上下两个凸壳。考虑通过一个个地扩展三角形的方式来得到这两个凸壳再合并。

我们使用 \(O(n^3(n+m))\) 的时间来预处理任意三个蓝点围成的三角形内是否存在红点以及有多少个蓝点。

然后我们令 \(f_{i,j,k}\) 表示从点 \(i\) 出发的上凸壳，目前最后一个点是 \(j\)，上一个点是 \(k\) 的情况下能够包含的最多的蓝点数目。

同理用 \(g_{i,j,k}\) 来表示下凸壳对应的内容。

这个很好转移，只需要枚举一个满足凸性的点就好了，然后利用预处理的值计算就好了。

最后合并上下凸壳也很方便，枚举左右顶点合并。还有就是 dp 计算过程中始终要保证三个点能够形成上/下凸壳。

时间复杂度 \(O(n^3(n+m))\)。

代码实现

达成成就，第一次在 TC 上做题。

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
#line 7 "RedAndBluePoints.cpp"
#include <functional>
#include <algorithm>
#include <stdexcept>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <utility>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <list>
#include <map>
#include <set>

using namespace std;

const int N=55;

inline int sgn(int x){return x?(x>0?1:-1):0;}

struct P
{
	int x,y;

	inline P(int x_=0,int y_=0){x=x_,y=y_;}

	inline bool operator<(P const p)const{return x<p.x||x==p.x&&y>p.y;}

	inline P operator+(P const p)const{return P(x+p.x,y+p.y);}
	inline P operator-(P const p)const{return P(x-p.x,y-p.y);}
	inline P operator*(int const k)const{return P(x*k,y*k);}

	inline int operator*(P const p)const{return x*p.x+y*p.y;}
	inline int operator^(P const p)const{return x*p.y-y*p.x;}
}blue[N],red[N];

inline bool in_triangle(P p,P a,P b,P c)
{
	return
	(
		sgn((c-a)^(p-a))*sgn((b-a)^(p-a))<=0
	&&	sgn((a-b)^(p-b))*sgn((c-b)^(p-b))<=0
	&&	sgn((b-c)^(p-c))*sgn((a-c)^(p-c))<=0
	);
}

int cnt[N][N][N],f[N][N][N],g[N][N][N];
int n,m;

inline void update(int &x,int y){x=x>y?x:y;}

class RedAndBluePoints
{
	public:
	int find(vector <int> blueX, vector <int> blueY, vector <int> redX, vector <int> redY)
	{
		memset(cnt,0,sizeof cnt),memset(f,0,sizeof f),memset(g,0,sizeof g);
		n=blueX.size(),m=redX.size();
		for (int i=0;i<n;++i) blue[i+1]=P(blueX[i],blueY[i]);
		for (int i=0;i<m;++i) red[i+1]=P(redX[i],redY[i]);
		sort(blue+1,blue+1+n);
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
				if (i!=j) for (int k=1;k<=n;++k)
					if (i!=k&&j!=k)
					{
						cnt[i][j][k]=0;
						for (int l=1;~cnt[i][j][k]&&l<=m;++l)
							if (in_triangle(red[l],blue[i],blue[j],blue[k])) cnt[i][j][k]=-1;
						if (~cnt[i][j][k])
							for (int l=1;l<=n;++l)
								if (in_triangle(blue[l],blue[i],blue[j],blue[k])) ++cnt[i][j][k];
					}
		for (int i=1;i<=n;++i)
			for (int j=i;j<=n;++j)
			{
				f[i][j][i]=g[i][j][i]=2;
				for (int k=i+1;k<j;++k)
					if (sgn((blue[j]-blue[i])^(blue[k]-blue[i]))<0) f[i][j][k]=-n*n;
					else for (int l=i;l<k;++l) if (~cnt[i][j][k]&&sgn((blue[j]-blue[k])^(blue[k]-blue[l]))>0) update(f[i][j][k],f[i][k][l]+cnt[i][j][k]-2);
				for (int k=i+1;k<j;++k)
					if (sgn((blue[j]-blue[i])^(blue[k]-blue[i]))>0) g[i][j][k]=-n*n;
					else for (int l=i;l<k;++l) if (~cnt[i][j][k]&&sgn((blue[k]-blue[l])^(blue[j]-blue[k]))>0) update(g[i][j][k],g[i][k][l]+cnt[i][j][k]-2);
			}
		int ret=1;
		for (int i=1;i<=n;++i)
			for (int a=i;a<=n;++a)
				for (int b=i;b<=n;++b)
					for (int j=max(a,b)+1;j<=n;++j)
						if (sgn((blue[j]-blue[i])^(blue[a]-blue[i]))>=0&&sgn((blue[j]-blue[i])^(blue[b]-blue[i]))<=0)
							update(ret,f[i][j][a]+g[i][j][b]-2);
		return ret;
	}
};