問題#
[NOIP2016 提高组] 愤怒的小鸟#
Kiana は最近、ある不思議なゲームに夢中になっています。
簡単に言うと、このゲームは平面上で行われます。
$(0,0)$ にある弾丸発射器から、Kiana は毎回第一象限に向かって赤い小鳥を発射できます。小鳥の飛行軌跡はすべて $y=ax^2+bx$ の形をした曲線であり、ここで $a,b$ は Kiana が指定するパラメータで、$a < 0$ でなければならず、$a,b$ は実数です。
小鳥が地面（つまり $x$ 軸）に戻ると、瞬時に消えます。
ゲームのあるレベルでは、平面の第一象限に $n$ 匹の緑の豚がいます。第 $i$ 匹の豚の座標は $\left (x_i,y_i \right)$ です。
もし小鳥の飛行軌跡が $\left (x_i, y_i \right)$ を通過した場合、第 $i$ 匹の豚は消滅し、小鳥は元の軌跡に沿って飛び続けます；
もし小鳥の飛行軌跡が $\left (x_i, y_i \right)$ を通過しなかった場合、その小鳥の飛行過程は第 $i$ 匹の豚に何の影響も与えません。
例えば、もし二匹の豚がそれぞれ $(1,3)$ と $(3,3)$ にいる場合、Kiana は飛行軌跡が $y=-x^2+4x$ の小鳥を発射することを選ぶことができ、そうすれば二匹の豚はその小鳥によって一緒に消滅します。
このゲームの目的は、小鳥を発射してすべての豚を消滅させることです。
この不思議なゲームの各レベルは Kiana にとって非常に難しいため、Kiana は自分がこのゲームをより簡単にクリアできるように、いくつかの神秘的な指令を入力しました。これらの指令は【入力形式】で詳述されます。
このゲームには合計 $T$ のレベルがあり、今 Kiana は各レベルで、すべての豚を消滅させるために少なくとも何匹の小鳥を発射する必要があるかを知りたいと思っています。彼女は計算ができないので、あなたに教えてほしいのです。
入力形式#
最初の行には正の整数 $T$ が含まれ、ゲームのレベルの総数を示します。
次に、$T$ の各レベルの情報が順に入力されます。各レベルの最初の行には二つの非負整数 $n,m$ が含まれ、それぞれそのレベルの豚の数と Kiana が入力した神秘的な指令のタイプを示します。次の $n$ 行には、第 $i$ 匹の豚の座標 $(x_i,y_i)$ を示す二つの正の実数 $x_i,y_i$ が含まれます。同じレベル内に完全に同じ座標の豚は存在しないことが保証されています。
もし $m=0$ の場合、Kiana は何の効果もない指令を入力したことを示します。
もし $m=1$ の場合、このレベルは次の条件を満たします：最大で $\lceil n/3 + 1 \rceil$ 匹の小鳥を使えばすべての豚を消滅させることができます。
もし $m=2$ の場合、このレベルは次の条件を満たします：必ず最適解が存在し、その中には少なくとも $\lfloor n/3 \rfloor$ 匹の豚を消滅させる小鳥が一匹含まれます。
$1\leq n \leq 18$、$0\leq m \leq 2$、$0 < x_i,y_i < 10$ であることが保証され、入力中の実数はすべて小数点以下二位まで保持されます。
上記の文中で、記号 $\lceil c \rceil$ と $\lfloor c \rfloor$ はそれぞれ $c$ を上に切り上げることと下に切り下げることを示します。例えば：$\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。
$(n \leq 18)$
解答#
n が 18 以下であることがわかるので、探索または状態圧縮を使用します。
状態圧縮 dp を使用し、f[S] を二進数状態で状態 S の豚を撃墜するために必要な最小の放物線の数と定義します。
任意の二点から構成される放物線がどの豚を撃墜できるかを前処理します。
状態を列挙する際、~ 問題の解答に従って～、各状態集合に対して最初に撃墜されていない豚を列挙するだけで済みます。
豚を撃墜する順序は結果に影響を与えません。
問題#
-
double が 0 かどうかを判断する ——
fabs(x) < eps -
double の正負を正常に比較する
-
ループが特に多い場合、初期化を間違った位置に置かないように注意する
コード#
#include<bits/stdc++.h>
using namespace std;
int T, n, m, a, b;
const double eps = 1e-6;
const int N = 19;
double x[N], y[N];
int lg[1 << N];
int lowbit[1 << N];
int f[1 << N];
int curve[N][N];
//int f[1 << N];
void getab(double &a, double &b, double x1, double y1, double x2, double y2)
{
a = (y2 * x1 - y1 * x2)/ (x1 * x2 * (x2 - x1));
b = (y2 * x1 * x1 - y1 * x2 * x2)/ (x1 * x2 * (x1 - x2));
}
int main()
{
for(int i = 2;i <= (1 << 18);i++)
{
lg[i] = lg[i >> 1] + 1;
}
for(int i = 0;i < (1 << 18);i++)
{
lowbit[i] = (~i & (-(~i)));
}
scanf("%d", &T);
while(T --)
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i++)
{
scanf("%lf%lf", &x[i], &y[i]);
}
double a, b;
memset(f, 0x3f, sizeof f);
memset(curve, 0, sizeof curve);
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
if(i == j || fabs(x[i] - x[j]) < eps) continue;
getab(a, b, x[i], y[i], x[j], y[j]);
if(a > 0) continue;
for(int k = 1;k <= n;k++)
{
if(fabs(a * x[k] * x[k] + b * x[k] - y[k]) < eps)
{
curve[i][j] |= (1 << (k - 1));
}
}
}
}
for(int i = 1;i <= n;i++)
curve[i][i] = (1 << (i - 1));
f[0] = 0;
for(int s = 0;s < (1 << n) - 1;s++)
{
for(int j = 1;j <= n;j++)
{
f[s | curve[lg[lowbit[s]] + 1][j]] = min(f[s | curve[lg[lowbit[s]] + 1][j]], f[s] + 1);
}
}
printf("%d\n", f[(1 << n) - 1]);
}
return 0;
}