NOI模拟题6 Problem C: Circle

Solution

首先这个矩阵, 很明显的就是Vandermonde矩阵. 我们有公式:

\[|F_n| = \prod_{1 \le j < i \le n} (a_i - a_j)
\]

套圈的半径, 显然就是最小圆覆盖问题.

考虑到数据范围比较大, 我们直接做肯定是不行的. 这时候就涉及到一个神奇的东西:

我们知道假如行列式的某两行相同, 则该行列式的值为\(0\). 考虑这道题, 我们发现它生成数据的方式非常奇怪, 假设生成\(x\)组询问, 则所有询问两两不相同的概率为

\[\prod_{k = n}^{n - x + 1} \frac k n
\]

这个概率会迅速地下降, 因此期望不需要太多的次数, 行列式的值就会变为\(0\)...

真是有意思...

#include <cstdio>

#include <cctype>

#include <cstdlib>

#include <cmath>

#include <algorithm>

using namespace std;

namespace Zeonfai

{

    inline int getInt()

    {

        int a = 0, sgn = 1; char c;

        while (! isdigit(c = getchar())) if (c == '-') sgn *= -1;

        while (isdigit(c)) a = a * 10 + c - '0', c = getchar();

        return a * sgn;

    }

}

const int N = (int)1e5, M = (int)1e5, MOD = (int)1e9 + 7;

struct point

{

    double x, y;

    inline point friend operator -(const point &a, const point &b) { point res; res.x = a.x - b.x; res.y = a.y - b.y; return res; }

    inline double friend operator *(const point &a, const point &b) { return a.x * b.y - a.y * b.x; }

}p[N + 1];

double r[M + 1];

int L[M + 1], R[M + 1];

inline double sqr(double a) { return a * a; }

inline double getDistance(point a, point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }

inline point getCentre(point a, point b, point c)

{

    point ret;

    double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2;

    double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2;

    double d = a1 * b2 - a2 * b1;

    ret.x = a.x + (c1 * b2 - c2 * b1) / d;

    ret.y = a.y + (a1 * c2 - a2 * c1) / d;

    return ret;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("circle.in", "r", stdin);

    freopen("circle.out", "w", stdout);

#endif

    using namespace Zeonfai;

    int n = getInt();

    for (int i = 1; i <= n; ++ i) p[i].x = getInt(), p[i].y = getInt();

    int m = getInt();

    int ans = 1;

    for (int i = 1; i <= m; ++ i)

    {

        L[i] = getInt(), R[i] = getInt();

        if (! ans) { printf("%lld\n", (long long)L[i] * R[i]); continue; }

        point cen = p[L[i]]; r[i] = 0;

        for (int j = L[i] + 1; j <= R[i]; ++ j) if (getDistance(p[j], cen) > r[i])

        {

            cen = p[j]; r[i] = 0;

            for (int k = L[i]; k < j; ++ k) if (getDistance(p[k], cen) > r[i])

            {

                cen.x = (p[j].x + p[k].x) / 2; cen.y = (p[j].y + p[k].y) / 2;

                r[i] = getDistance(p[j], cen);

                for (int l = L[i]; l < k; ++ l) if (getDistance(p[l], cen) > r[i])

                {

                    if ((p[k] - p[j]) * (p[l] - p[j]) == 0)

                    {

                        cen.x = (p[j].x + p[l].x) / 2; cen.y = (p[j].y + p[l].y) / 2;

                        r[i] = getDistance(p[l], cen);

                    }

                    else cen = getCentre(p[j], p[k], p[l]), r[i] = getDistance(p[l], cen);

                }

            }

        }

        for (int j = 1; j < i; ++ j) ans = (long long)ans * ((long long)r[i] - (long long)r[j] + MOD) % MOD;

        printf("%lld\n", (long long)ans + L[i] * R[i]);

    }

巴特西

NOI模拟题6 Problem C: Circle

Solution

最新文章

热门文章