| by XianKa | No comments

【计算几何-技巧】射击游戏

Description
js在ak了一套cf后,打开了一款新出的射击游戏。

这个射击游戏在一个二维平面进行,js控制的人物处于坐标原点(0,0)。平面上共有n只怪物,每个怪物所在的坐标为(x[i], y[i])。js进行一次射击会把x轴和y轴上(包含坐标原点)的怪物一次性消灭。

而高贵的js是这个游戏的VIP玩家,他拥有两项特权操作:
1、让平面内的所有怪物向任意一个相同的方向移动相同的距离d。
2、让平面内的所有怪物以js为中心旋转相同的角度θ。

js在进行射击前,可以无限次的使用这两项特权操作。js想知道在他射击的时候最多可以同时消灭多少只怪物,请你帮帮伟大的js吧。

Input
输入包括三行。

第一行中有一个正整数n(1 <= n <= 100),表示平面内的怪物数量。

第二行包括n个由空格分隔的整数x[i](-1,000,000 <= x[i] <= 1,000,000),表示每只怪物的横坐标。

第二行包括n个由空格分隔的整数y[i](-1,000,000 <= y[i] <= 1,000,000),表示每只怪物的纵坐标。

Output
输出js一次性最多能消灭的怪物数。

Sample Input
5
0 -1 1 1 -1
0 -1 -1 1 1
Sample Output
5

枚举两个点,连成一条线。每次检查在线上有多少点,不在线上的点往线上作投影,当线上的点+某个投影的坐标的所有点>答案的时候,更新答案。

是否三点一线用向量是否平行,投影也用向量坐标运算。

技巧:投影用map来存储,遍历的时候用map的迭代器进行遍历。重载运算符实现坐标相减得到向量的功能。

答案初始化为1;因为如果没有能构成线点,那么将不运算

#include<bits/stdc++.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
struct point{
	ll x, y;
	point(){}
	point(ll x,ll y):x(x),y(y){}
	point operator -(point tp)
	{
		return point(x-tp.x,y-tp.y);
	}
}p[110];
ll dot(point a,point b)
{
	return a.x*b.x+a.y*b.y;
}
ll cross(point a,point b)
{
	return a.x*b.y-b.x*a.y;
}
ll on(point a,point b,point c)
{
	return cross(c-a,c-b)==0;
}
int main()
{
	ll n;
	ll ans=1;
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++)
	{
		scanf("%lld",&p[i].x);
	}
	for(ll i=1;i<=n;i++)
	{
		scanf("%lld",&p[i].y);
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=i+1;j<=n;j++)
		{
			ll cnt=0;
			map<ll,ll> cnt2;
			point v=p[j]-p[i];
			for(ll k=1;k<=n;k++)
			{
				if(on(p[i],p[j],p[k])) cnt++;
				else cnt2[dot(v,p[k])]++;
			}
			ans=max(ans,cnt);
			for(map<ll,ll>::iterator it=cnt2.begin();it!=cnt2.end();it++ )
			{
				ans=max(ans,cnt + it->second );
			}
		}
	}
	printf("%lld",ans);
} 

 

发表评论