tokitsukaze > Codeforces Round#488 div2E/div1C Careful Maneuvering (枚举)

Codeforces Round#488 div2E/div1C Careful Maneuvering (枚举)

2018-06-17

枚举

转载请注明出处：http://tokitsukaze.live/

题目链接：http://codeforces.com/problemset/problem/993/C

题意：在一个平面上有两组点。第一组的横坐标为x=-100，并且没有相同的y。第二组的横坐标为x=100，并且没有相同的y。现在要在x=0处放两个点(可以放在同一个坐标上)，对于那两组点，每一组的点都会对这两个点做射线，并可能命中另一组的点。求命中点的个数最大是多少。

题解：
那两个点肯定是在第一组的某个点和第二组的某个点的连线上。所以先枚举每一对点(为了避免出现小数，输入的每个点的y先X2)，连线与x=0相交求出交点A。然后每个点对A做射线，如果能命中另一组的点，就状压标记一下这个点和命中的点。这里的复杂度是O(n^3*log(n))。

然后再暴力枚举两个交点，计算一下两个交点总共能命中多少个点，取max即可。状压我用了bitset(可以直接用ll)，这里的复杂度是O(n^5/64)，其实就是O(n^4)。

代码：

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
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace std;
#define _GLIBCXX_PERMIT_BACKWARD_HASH
#include <ext/hash_map>
using namespace __gnu_cxx;
struct str_hash{size_t operator()(const string& str)const{return __stl_hash_string(str.c_str());}};
typedef long long ll;
typedef unsigned long long ull;
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDD pair<double,double>
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-8;
const int MAX=1e5+10;
const ll mod=1e9+7;
int n,m,a[111],b[111];
hash_map<int,int> aa,bb;
bitset<65> aaa[62][62],bbb[62][62];
void gao(int x,int ii,int jj)
{
	
	int i,tmp;
	for(i=1;i<=n;i++)
	{
		tmp=a[i]+2*(x-a[i]);
		if(bb.count(tmp))
		{
			aaa[ii][jj][i]=1;	
			bbb[ii][jj][bb[tmp]]=1;	
		}
	}
	for(i=1;i<=m;i++)
	{
		tmp=b[i]+2*(x-b[i]);
		if(aa.count(tmp))
		{
			aaa[ii][jj][aa[tmp]]=1;
			bbb[ii][jj][i]=1;	
		}
	}
}
int main()
{
	int i,j,ans,ii,jj;
	while(~scanf("%d%d",&n,&m))
	{
		aa.clear();
		bb.clear();
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			a[i]*=2;
			aa[a[i]]=i;
		}
		for(i=1;i<=m;i++)
		{
			scanf("%d",&b[i]);
			b[i]*=2;
			bb[b[i]]=i;
		}
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				aaa[i][j].reset();
				bbb[i][j].reset();
				gao(max(a[i],b[j])-abs(a[i]-b[j])/2,i,j);
			}
		}
		ans=0;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				for(ii=i;ii<=n;ii++)
				{
					for(jj=j;jj<=m;jj++)
					{
						ans=max(ans,(int)(aaa[i][j]|aaa[ii][jj]).count()+(int)(bbb[i][j]|bbb[ii][jj]).count());
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}