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;
}