求调
查看原帖
求调
551158
bys222楼主2025/7/30 19:52

代码样例二过不了

#include <bits/stdc++.h>
#define db double
using namespace std;
const db eps = 1e-6;
const int maxn = 20;
const int maxx = 400;
int n, m, a[maxx], dp[1 << 18];
db x[maxn], y[maxn];
int main ()
{
    int T;
    cin >> T;
    while (T--)
    {
        memset(dp, 0x3f, sizeof(dp));
        memset(a, 0, sizeof(a));
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                if (x[i] != x[j])
                {
                    db t1 = (y[i] * x[j] - y[j] * x[i]) / (x[i] * x[j] * (x[i] - x[j]));
                    db t2 = (y[i] - t1 * x[i] * x[i]) / x[i];
                    if (t1 < 0)
                    {
                        cnt++;
                        for (int k = 1; k <= n; k++)
                        {
                            if (fabs(t1 * x[k] * x[k] + t2 * x[k] - y[k]) <= eps) a[cnt] |= (1 << k - 1);
                        }
                    }
                }
            }
        }
        dp[0] = 0;
        for (int i = 0; i < (1 << n); i++)
        {
            for (int j = 1; j <= cnt; j++) dp[i | a[j]] = min(dp[i | a[j]], dp[i] + 1);
            for (int j = 1; j <= n; j++) dp[i | (1 << j - 1)] = min(dp[i | (1 << j - 1)], dp[i] + 1);
        }
        cout << dp[(1 << n) - 1] << endl;
    }
    return 0;
}
2025/7/30 19:52
加载中...