rockdu
There are two small spaceship, surrounded by two groups of enemy larger spaceships. The space is a two-dimensional plane, and one group of the enemy spaceships is positioned in such a way that they all have integer yy-coordinates, and their xx-coordinate is equal to −100−100, while the second group is positioned in such a way that they all have integer yy-coordinates, and their xx-coordinate is equal to 100100.
Each spaceship in both groups will simultaneously shoot two laser shots (infinite ray that destroys any spaceship it touches), one towards each of the small spaceships, all at the same time. The small spaceships will be able to avoid all the laser shots, and now want to position themselves at some locations with x=0x=0 (with not necessarily integer yy-coordinates), such that the rays shot at them would destroy as many of the enemy spaceships as possible. Find the largest numbers of spaceships that can be destroyed this way, assuming that the enemy spaceships can't avoid laser shots.
The first line contains two integers nn and mm (1≤n,m≤601≤n,m≤60), the number of enemy spaceships with x=−100x=−100 and the number of enemy spaceships with x=100x=100, respectively.
The second line contains nn integers y1,1,y1,2,…,y1,ny1,1,y1,2,…,y1,n (|y1,i|≤10000|y1,i|≤10000) — the yy-coordinates of the spaceships in the first group.
The third line contains mm integers y2,1,y2,2,…,y2,my2,1,y2,2,…,y2,m (|y2,i|≤10000|y2,i|≤10000) — the yy-coordinates of the spaceships in the second group.
The yy coordinates are not guaranteed to be unique, even within a group.
Print a single integer – the largest number of enemy spaceships that can be destroyed.
3 91 2 31 2 3 7 8 9 11 12 13
9
5 51 2 3 4 51 2 3 4 5
10
In the first example the first spaceship can be positioned at (0,2)(0,2), and the second – at (0,7)(0,7). This way all the enemy spaceships in the first group and 66 out of 99 spaceships in the second group will be destroyed.
In the second example the first spaceship can be positioned at (0,3)(0,3), and the second can be positioned anywhere, it will be sufficient to destroy all the enemy spaceships.
注意到n, m都只有60，并且只有两两连线与y = 0的交点才有可能击毁飞船(2艘)。那么我们直接枚举n^2个交点，把每个交点能击毁的A飞船和B飞船分别加入两个longlong中。我我们就是要选出两个交点，使它们的两个longlong或起来的"1"最多。直接n^4枚举就行了。
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 1e5 + 5, B = 20000;
int a[maxn], b[maxn], asc, mx, n, m, Acnt, Bcnt, tmp;
vector<int > Apos[maxn], Bpos[maxn];
LL AScm[maxn], BScm[maxn], pow[maxn], ans[maxn][3];
inline int sym(int p, int x2) {return x2 - p;}
inline bool lg(int p) {return p >= -10000 && p <= 10000;}
int Cone(LL a, LL b) {
int ans = 0;
while(a) ans += a & 1, a >>= 1;
while(b) ans += b & 1, b >>= 1;
return ans;
}
int main() {
scanf("%d%d", &n, &m);
For(i, 1, n) scanf("%d", &a[i]), Apos[a[i] + B].push_back(i);
For(i, 1, m) scanf("%d", &b[i]), Bpos[b[i] + B].push_back(i);
For(i, 0, 61) pow[i] = 1LL << i;
For(x, -20000, 20000) {
For(i, 1, n) if(lg(tmp = sym(a[i], x)))
for(register int j = Bpos[tmp + B].size() - 1; j >= 0; --j)
BScm[x + B] |= pow[Bpos[tmp + B][j] - 1];
For(i, 1, m) if(lg(tmp = sym(b[i], x)))
for(register int j = Apos[tmp + B].size() - 1; j >= 0; --j)
AScm[x + B] |= pow[Apos[tmp + B][j] - 1];
if((AScm[x + B] | BScm[x + B]))
ans[++asc][0] = AScm[x + B], ans[asc][1] = BScm[x + B];
}
For(i, 1, asc)
For(j, i, asc)
mx = max(mx, Cone(ans[i][0] | ans[j][0], ans[i][1] | ans[j][1]));
printf("%d", mx);
return 0;
}
没有帐号? 立即注册