【题目描述】 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想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。 【输入格式】 第一行包含一个正整数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，输入中的实数均保留到小数点后两位。 上文中，符号和分别表示对x向上取整和向下取整。 【输出格式】 对每个关卡依次输出一行答案。 输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。 【样例输入】 3 2 0 1.41 2.00 1.73 3.00 3 0 1.11 1.41 2.34 1.79 2.98 1.49 5 0 2.72 2.72 2.72 3.14 3.14 2.72 3.14 3.14 5.00 5.00 【输出格式】 2 2 3 【分析】 因为n的范围很小，所以直接暴搜即可。 其实这个m的用处并不大，顶多当成一个剪枝。
type ar=array[1..2]of real; var t,i,j,n,m,ans,sh:longint; s:array[1..18,1..18,1..2]of real; x,y:array[1..18]of real; bz:array[1..18]of boolean; bzz:array[0..262144]of longint; w:array[0..18]of longint; function pdd(x,y:real):boolean;//注意精度，如果误差在1e-6以下完全可以认为是可行的 begin if round(x*1000000)=round(y*1000000)then exit(true); exit(false); end; function pd(x,y:ar):boolean; begin if pdd(x[1],y[1])and pdd(x[2],y[2])then exit(true);exit(false); end; procedure find(xx,sum:longint);//尝试打死第xx只猪，当前共用了sum只小鸟 var i,j,ysh:longint; yl:array[1..18]of boolean; begin if sum>=ans then exit; while (xx<=n)and(bz[xx]) do inc(xx); if xx=n+1 then begin ans:=sum;exit; end; if xx<n then begin sh:=sh+w[xx]; for i:=xx+1 to n do if not bz[i]and(s[xx,i,1]<0) then begin yl:=bz;ysh:=sh;bz[i]:=true;sh:=sh+w[i]; for j:=i+1 to n do if not bz[j]and(pd(s[xx,i],s[i,j]))then begin bz[j]:=true;sh:=sh+w[j]; end; if sum+1<bzz[sh]then begin bzz[sh]:=sum+1;find(xx+1,sum+1); end; bz:=yl;sh:=ysh; end; sh:=sh-w[xx]; end; sh:=sh+w[xx]; if sum+1<bzz[sh] then begin bzz[sh]:=sum+1;find(xx+1,sum+1); end; sh:=sh-w[xx]; end; function suan(x,y,x2,y2:real):ar; begin if not pdd(x2,x) then begin suan[1]:=(y2-y*x2/x)/(x2*x2-x*x2); suan[2]:=(y-suan[1]*x*x)/x; end else begin suan[2]:=(x2-x*y2/y)/(y2*y2-y*y2); suan[1]:=(x-suan[2]*y*y)/y; end; end; begin readln(t); w[1]:=1; for i:=2 to 18 do w[i]:=w[i-1]*2; for t:=1 to t do begin readln(n,m); for i:=0 to 1<<n do bzz[i]:=n+1; for i:=1 to n do begin readln(x[i],y[i]); for j:=1 to i-1 do s[j,i]:=suan(x[j],y[j],x[i],y[i]); end; ans:=n+1; sh:=0; find(1,0); writeln(ans); end; end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533482.html
