P2831 [NOIP2016 提高组] 愤怒的小鸟

思路：

考虑先求出经过 \((x_1,y_1),(x_2,y_2)\) 的抛物线解析式

我们有：

\[\begin{cases} ax_1^2 + bx_1 = y_1 \\ ax_2^2 + bx_2 = y_2\end{cases} \]

考虑将 \(b\) 消掉，求出 \(a\)。

那么考虑令 \(1\) 式减去 \(2\) 式的 \(\frac{x_1}{x_2}\) 倍：

\[ax_1^2 + bx_1 – ax_1x_2 – bx_1 = y_1 – \frac{x_1}{x_2} y_2 \]

\[a(x_1^2 -x_1x_2) = y_1 – \frac{x_1}{x_2} y_2 \]

\[a = \frac{y_1 – \frac{x_1}{x_2} y_2}{x_1^2 -x_1x_2} = \frac{y_1x_2 – x_1 y_2}{x_1^2x_2 – x_1x_2^2} \]

因为 \(a\) 太复杂度，不好带入，考虑也将 \(a\) 消掉，求出 \(b\)。

那么考虑令 \(1\) 式减去 \(2\) 式的 \(\frac{x_1^2}{x_2^2}\) 倍：

\[ax_1^2 + bx_1 – ax_1^2 – b\frac{x_1^2}{x_2} = y_1 – y_2 \frac{x_1^2}{x_2^2} \]

\[b(x_1 – \frac{x_1^2}{x_2}) = y_1 – y_2 \frac{x_1^2}{x_2^2} \]

\[b = \frac{y_1 – y_2 \frac{x_1^2}{x_2^2}}{x_1 – \frac{x_1^2}{x_2}} = \frac{y_1x_2^2 – y_2 x_1^2}{x_1x_2^2 – x_1^2 x_2} \]

那么我们可以得到经过 \((x_1,y_1),(x_2,y_2)\) 的抛物线解析式为：

\[y = \frac{y_1x_2 – x_1 y_2}{x_1^2x_2 – x_1x_2^2} x^2 + \frac{y_1x_2^2 – y_2 x_1^2}{x_1x_2^2 – x_1^2 x_2} x \]

可以通过这个解析式求出其它在这个抛物线上的点，设 \(A_{i,j}\) 表示经过点 \(i\) 和点 \(j\) 的抛物线经过的所有点的点集。

考虑状态压缩 dp，令 \(dp_S\) 表示 \(S\) 这个点集的鸟被射下来的最小次数，则：

\[dp_0 = 0 \]

\[dp_{S \operatorname{or} A_{i,j}} = \min(dp_{S \operatorname{or} A_{i,j}},dp_S + 1) \]

\[dp_{S \operatorname{or} 2^{i-1}} = \min(dp_{S \operatorname{or} 2^{i-1}},dp_S+1) \]

时间复杂度为 \(O(Tn^22^n)\)。

完整代码：

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=19,M=(1ll<<N)+10;
const db Eps=1e-6;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll T,n;
ll a[N][N];
ll dp[M];
db x[N],y[N];
pair<db,db> get(db x1,db y1,db x2,db y2){
	db a=(y1*x2-x1*y2)/(x1*x1*x2-x1*x2*x2);
	db b=(y1*x2*x2-y2*x1*x1)/(x1*x2*x2-x1*x1*x2);
	return {a,b};
}
db get(db x,db a,db b){
	return a*x*x+b*x;
}
void solve(){
	memset(dp,0x7f,sizeof(dp));
	n=read(),read();
	for(int i=1;i<=n;i++)
	  scanf("%lf%lf",&x[i],&y[i]);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			a[i][j]=0;
			auto t=get(x[i],y[i],x[j],y[j]);
			if(t.fi>=0)
			  continue;
			for(int k=1;k<=n;k++){
				db h=get(x[k],t.fi,t.se);
				if(abs(h-y[k])<=Eps)
				  a[i][j]|=(1ll<<(k-1));
			}
		}
	} 
	dp[0]=0;
	for(int S=0;S<(1ll<<n);S++){
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if((a[i][j]&S)==a[i][j])
				  continue;
				dp[S|a[i][j]]=min(dp[S|a[i][j]],dp[S]+1);
			}
		}
		for(int i=1;i<=n;i++)
		  dp[S|(1ll<<(i-1))]=min(dp[S|(1ll<<(i-1))],dp[S]+1);
	} 
	write(dp[(1ll<<n)-1]);
	putchar('\n');
}
bool End;
int main(){
	T=read();
	while(T--)
	  solve();
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}