题目
Description
https://www.luogu.org/problem/show?pid=2831
Kiana最近沉迷于一款神奇的游戏无法自拔。
简单来说，这款游戏是在一个平面上进行的。
有一架弹弓位于(0,0)处，每次Kiana可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如y = ax^2 + bx的曲线，其中a, b是Kiana指定的参数，且必须满足a<0。
当小鸟落回地面(即x轴)时，它就会瞬间消失。
在游戏的某个关卡里，平面的第一象限中有n只绿色的小猪，其中第i只小猪所在的坐标为(xi,yi)。
如果某只小鸟的飞行轨迹经过了(xi,yi)，那么第i只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行;
如果一只小鸟的飞行轨迹没有经过(xi,yi)，那么这只小鸟飞行的全过程就不会对第i只小猪产生任何影响。
例如，若两只小猪分别位于(1, 3 )和(3, 3 )
Kiana可以选择发射一只飞行轨迹为y=-x^2+ 4x的小鸟，这样两只小猪就会被这只小鸟一起消灭。
而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对Kiana来说都很难，所以Kiana还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。
假设这款游戏一共有T个关卡，现在Kiana想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。
Input
输入格式：
第一行包含一个正整数T，表示游戏的关卡总数。
下面依次输入这T个关卡的信息。每个关卡第一行包含两个非负整数n,m，分别表示该关卡中的小猪数量和Kiana输入的神秘指令类型。接下来的n行中，第i行包含两个正实数(xi,yi)，表示第i只小猪坐标为(xi,yi)。数据保证同一个关卡中不存在两只坐标完全相同的小猪。
如果m=0，表示Kiana输入了一个没有任何作用的指令。
如果m=1，则这个关卡将会满足：至多用只小鸟即可消灭所有小猪。
如果m=2,则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少只小猪。
保证1<=n<=18，0<=m<=2，0< xi,yi<10，输入中的实数均保留到小数点后两位。
上文中，符号和分别表示对c向上取整和向下取整
Output
对每个关卡依次输出一行答案。
输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。
题解
题目没有贴全，样例也没有打了（到Luogu上去看）
这道题目。。。。怎么说。。。。其实有点水。
作为Tg的D2T3确实偏简单了一些（T2有毒）
我的思路比较暴力：每次强行枚举任意两只猪，算出其抛物线（判断是否合法），计算出最多能够消灭几只猪（使用状压存状态）。最后再添加一个单独消灭某只猪的DFS。强暴DFS计算。
至于优化，我加了一个记忆化搜索和对ans的剪枝。
这题的思路十分暴力，我在CJOJ上很快就AC了
不知道再别的OJ上是不是AC的（没有试，很可能被卡精度）
希望诸位dalao帮我测一测
如果Wa了，也请各位dalao帮我查一下错误，谢谢了
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX=25;
double A,B;
int ans;
int n,m,T;
int f[MAX][(1<<20)];//记忆化
inline void solve(int i,int j);//求解抛物线
struct Pig
{
double x,y;
}P[MAX];
bool operator <(Pig a,Pig b)
{
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
inline void DFS(int x,int t,int b)//还有x只猪没被消灭，t用来存储消灭情况
{
if(x<=1)//只有一直猪也只接判断
{
ans=min(ans,b+x);//b用来储存鸟的数量
return;
}
if(b>=ans-1)return;
if(f[x][t]!=0)
{
if(b>=f[x][t])return;
else
f[x][t]=b;
}
else
f[x][t]=b;
for(int i=1;i<=n;++i)
{
int tt=t,kk=0;
if((1<<(i-1))&t)//这只猪已经死了
continue;
for(int j=i+1;j<=n;++j)
{
if((1<<(j-1))&t)//这只猪也死了
continue;
tt= t|(1<<(i-1));
tt=tt|(1<<(j-1));
kk=2;
solve(i,j);//求解这两只猪所在的抛物线
if(A>=-0.001||B<=0.001)continue;//不合题意的抛物线
for(int k=1;k<=n;++k)//检查是否有猪在这条抛物线上
{
if(!(tt&(1<<(k-1))))//猪没有死才检查
{
double yy=P[k].x*(A*P[k].x+B);
if(fabs(yy-P[k].y)<=0.0001)//如果能够打死(卡下精度)
{
kk+=1;
tt=tt|(1<<(k-1));
}
// if(yy<=0)//这只鸟已经没了
// break;
}
}
DFS(x-kk,tt,b+1);
}
DFS(x-1,t|(1<<(i-1)),b+1);//单独弄死
}
}
int main()
{
cin>>T;
while(T--)
{
memset(f,0,sizeof(f));
cin>>n>>m;
if(m==0)ans=n;
if(m==1)ans=n/3+1;
if(m==2)ans=1+(n-n/3);
for(int i=1;i<=n;++i)
cin>>P[i].x>>P[i].y;
DFS(n,0,0);
cout<<ans<<endl;
}
}
inline void solve(int i,int j)
{
double a1=P[i].x*P[i].x;
double a2=P[j].x*P[j].x;
double b1=P[i].x;
double b2=P[j].x;
double c1=P[i].y;
double c2=P[j].y;
double tt=a1/a2;
a2=a1;b2*=tt;c2*=tt;//把a的系数化成一样的
if(fabs(b2-b1)<=0.001)//不能够除以0
{
B=-1000;
A=+1000;
return;
}
B=(c2-c1)/(b2-b1);//加减消元求B
if(fabs(a1)<=0.001)//不能够除以0
{
B=-1000;
A=+1000;
return;
}
A=(c1-B*b1)/a1;//代入消元求A
}