RT,我在本地和洛谷在线 IDE 运行样例 #10
,全部是正确的:
10
9
10
9
10
但是提交后给我报的错是酱:
Wrong Answer.wrong answer On line 1 column 1, read 0, expected 1.
请问这是为什么?
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 18, K = (1 << N);
const double eps = 1e-6;
int n, m;
double x[N], y[N];
int f[K + 10], ln[N][N];
int ft[K + 10];
void get_line (double &a, double &b, double x, double y, double X, double Y)
{
a = -(y * X - Y * x) / (x * X * X - x * x * X);
b = (y * X * X - Y * x * x) / (x * X * X - x * x * X);
}
// void equation (double &a, double &b, int i, int j)
// {
// a = -(y * X - Y * x) / (X * X * x - x * x * X);
// b = (y * X * X - Y * x * x) / (x * X * X - X * x * x);
// }
void solve()
{
scanf ("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf ("%lf%lf", &x[i], &y[i]);
memset (ln, 0, sizeof ln);
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
if (x[i] == x[j])
continue;
double a, b;
get_line (a, b, x[i], y[i], x[j], y[j]);
if (a > -eps)
continue;
for (int k = 1; k <= n; k++)
{
// printf ("%d %.6f %.6f %.6f\n", k, x[k], y[k], a * x[k] * x[k] + b * x[k]);
if (fabs (a * x[k] * x[k] + b * x[k] - y[k]) < eps)
ln[i][j] |= (1 << k - 1);
}
ln[j][i] = ln[i][j];
// printf ("%d-%d %d: %.6f %.6f\n", i, j, ln[i][j], a, b);
}
}
for (int s = 0; s < (1 << n); s++)
{
for (int i = 1; i <= n; i++)
{
if ((s & (1 << i - 1)) == 0)
{
ft[s] = i;
break;
}
}
}
memset (f, 0x3f, sizeof f);
f[0] = 0;
for (int s = 0; s < (1 << n); s++)
{
// printf ("%d %d\n", s, f[s]);
int i = ft[s];
for (int j = i + 1; j <= n; j++)
{
if (s & (1 << j - 1))
continue;
f[s | ln[i][j]] = min (f[s | ln[i][j]], f[s] + 1);
}
for (int j = 1; j <= n; j++)
{
if (s & (1 << j - 1))
continue;
f[s | (1 << j - 1)] = min (f[s | (1 << j - 1)], f[s] + 1);
}
}
printf ("%d\n", f[(1 << n) - 1]);
}
int main()
{
int T;
scanf ("%d", &T);
while (T--)
solve();
return 0;
}