题解 CF698D 【Limak and Shooting Points】
VenusM1nT
2020-10-19 21:14:08
非常有趣的一道题。因为题面问的是多少怪“可能”被击中，所以只需要对于每个怪分别考虑它可不可能被击中就好了。假定当前考虑第 $b_1$ 个怪，第 $a_1$ 个人击杀了这个怪，但 $a_1\to b_1$ 的路径上可能有若干个怪，比如有 $b_2$ 怪，那么就需要其他人来杀死这个怪，假定 $a_2$ 击杀了 $b_2$，但 $a_2\to b_2$ 的路径上可能有 $b_3$ 怪，那么就需要 $a_3$ 来击杀这个怪……以此类推无限~~套娃~~递推，跑个 Dfs 就可以了。排列方式 $k!$ 种，分别 $k$ 个人，$n$ 个怪，复杂度 $\text{O}(k!\times nk)$。
以上是主做法，这里提一嘴怎么判断 $a_i \to b_j$ 打不打得到，考虑两个怪 $B=(x_1,y_1),C=(x_2,y_2)$，一个人 $A=(x_3,y_3)$，假设 $A\to B$，无脑做法就是计算斜率 $k=\frac{\Delta y}{\Delta x}$ 然后列方程，但其实还有一种方法，考虑向量 $\overrightarrow{AB},\overrightarrow{AC}$，若有 $\overrightarrow{AB}\times\overrightarrow{AC}=0$，则 $A,B,C$ 共线，此时还有一种可能就是 $C$ 不在 $A,B$ 之间，于是考虑向量 $\overrightarrow{CA},\overrightarrow{CB}$，若 $\overrightarrow{CA}\cdot\overrightarrow{CB}<0$，此时 $\theta=\pi$，$C$ 必然在 $A,B$ 之间。这样做避免了精度损失而且简洁。
```cpp
#include<bits/stdc++.h>
#define N 1000
#define K 7
#define reg register
#define inl inline
#define int long long
using namespace std;
struct Vec
{
int x,y;
friend Vec operator - (const Vec &a,const Vec &b)
{
return ((Vec){a.x-b.x,a.y-b.y});
}
friend int operator * (const Vec &a,const Vec &b)
{
return a.x*b.x+a.y*b.y;
}
friend int operator ^ (const Vec &a,const Vec &b)
{
return a.x*b.y-a.y*b.x;
}
}a[K+5],b[N+5];
vector <int> t[K+5][N+5];
int k,n,idx,tot,id[K+5],c[N+5];
bool vis[K+5];
inl bool Check(reg int x)
{
if((++tot)>k) return 0;
if(t[id[tot]][x].empty())
{
c[x]=idx;
return 1;
}
reg int tmp=tot;
for(auto v : t[id[tmp]][x])
{
if(c[v]!=idx)
{
if(!Check(v)) return 0;
}
}
c[x]=idx;
return 1;
}
bool Dfs(reg int u,reg int v)
{
if(u>k)
{
idx++;
tot=0;
return Check(v);
}
for(reg int i=1;i<=k;i++)
{
if(!vis[i])
{
vis[i]=1;
id[u]=i;
if(Dfs(u+1,v)) return 1;
vis[i]=0;
}
}
return 0;
}
signed main()
{
scanf("%lld %lld",&k,&n);
for(reg int i=1;i<=k;i++) scanf("%lld %lld",&a[i].x,&a[i].y);
for(reg int i=1;i<=n;i++) scanf("%lld %lld",&b[i].x,&b[i].y);
for(reg int i=1;i<=k;i++)
{
for(reg int j=1;j<=n;j++)
{
for(reg int l=1;l<=n;l++)
{
if(j==l) continue;
if(!((a[i]-b[j])^(b[l]-b[j])) && (a[i]-b[j])*(b[l]-b[j])<0) t[i][l].push_back(j);
}
}
}
reg int ans=0;
for(reg int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(Dfs(1,i)) ans++;
}
printf("%lld\n",ans);
return 0;
}
```