转载请注明出处: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;
}