1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
int T;
int N, M;
double x[19], y[19];
int curve[19][19];
int f[524289];
inline void equals(double& a, double& b, double x1, double y1, double x2, double y2) {
a = (y1 * x2 - x1 * y2) / (x1 * x1 * x2 - x2 * x2 * x1);
b = (y1 - x1 * x1 * a) / x1;
}
inline int dp(int s) {
if (f[s] != -1) return f[s];
if (s == (1 << N) - 1) return f[s] = 0;
f[s] = INF;
for (register int i = 1; i <= N; ++i) {
for (register int j = i; j <= N; ++j) {
f[s] = min(f[s], dp(s | curve[i][j]) + 1);
}
}
return f[s];
}
int main() {
scanf("%d", &T);
while (T--) {
memset(curve, 0, sizeof(curve));
scanf("%d%d", &N, &M);
for (register int i = 1; i <= N; ++i)
scanf("%lf%lf", &x[i], &y[i]);
for (register int p1 = 1; p1 <= N; ++p1) {
for (register int p2 = p1 + 1; p2 <= N; ++p2) {
double a, b;
equals(a, b, x[p1], y[p1], x[p2], y[p2]);
if (a >= 0) continue;
for (register int i = 1; i <= N; ++i) {
if (x[i] * x[i] * a + x[i] * b >= y[i] - EPS && x[i] * x[i] * a + x[i] * b <= y[i] + EPS) {
curve[p1][p2] |= (1 << (i - 1));
curve[p2][p1] |= (1 << (i - 1));
}
}
}
}
for (register int p = 1; p <= N; ++p)
curve[p][p] = (1 << (p - 1));
memset(f, -1, sizeof(f));
printf("%d\n", dp(0));
}
return 0;
}
|