Codeforces Round #338 (Div. 2)

题目链接：https://codeforces.com/contest/615

A - Link/Cut Tree

这题目的title有点吓人啊。

题意：给一个区间 \([l,r](1\leq l \leq r \leq 10^{18})\) 和一个数 \(k(1\leq k \leq 10^9)\) ，问 \([l,r]\) 中 \(k\) 的幂分别是。

小心溢出。

ll ans[1005];
int atop;

void test_case() {
    ll l, r, k, p = 1;
    scanf("%lld%lld%lld", &l, &r, &k);
    atop = 0;
    while(p <= r) {
        if(p >= l)
            ans[++atop] = p;
        if(r / p < k)
            break;
        else
            p *= k;
    }
    if(atop == 0)
        puts("-1");
    else {
        for(int i = 1; i <= atop; ++i)
            printf("%lld%c", ans[i], " \n"[i == atop]);
    }
}

B - Gena‘s Code

题意：给 \(n(1\leq n \leq 10^5)\) 个数字，其中至少 \(n-1\) 个数字满足只有最高位是1，其他位都是0。求他们的乘积。

题解：找出那个可能存在的与众不同的数，在它后面加上0。

char s[100005];
char t[100005];

void test_case() {
    int n;
    scanf("%d", &n);
    int sum0 = 0, mett = 0;
    for(int i = 1; i <= n; ++i) {
        scanf("%s", s);
        int l = strlen(s);
        int suc = 1, cnt1 = 0, cnt0 = 0;
        for(int j = 0; j < l; ++j) {
            if(s[j] == '1') {
                ++cnt1;
                if(cnt1 >= 2) {
                    suc = 0;
                    break;
                }
            } else if(s[j] != '0') {
                suc = 0;
                break;
            } else
                ++cnt0;
        }
        if(cnt0 == l) {
            puts("0");
            return;
        }
        if(!suc) {
            strcpy(t, s);
            mett = 1;
        } else
            sum0 += cnt0;
    }
    if(mett)
        printf("%s", t);
    else
        putchar('1');

    while(sum0--)
        putchar('0');
    putchar('\n');
}

C - Peter and Snow Blower

题意：一台凸多边形的除雪机，凸多边形按逆时针顺序给出，把它栓在一根柱子P上，然后它会绕着柱子旋转，把覆盖到的位置的雪擦除。问擦除的雪的面积。

题解：显然擦除的面积是一个圆环，且外沿必定是离P最远的凸多边形的顶点，但是内沿有可能是凸多边形的某条边绕P旋转一次得到的。所以求出每条边到P的距离，取最小值就可以得到内沿半径。最后根据 \(S=\pi R^2\) 求出圆的面积然后作差。

突然发现没有计算几何的模板。

double x[100005], y[100005];

struct Point {
    double x, y;
    Point (double xx = 0, double yy = 0) {
        x = xx;
        y = yy;
    }
    friend Point operator-(const Point &a, const Point &b) {
        return Point(a.x - b.x, a.y - b.y);
    }
    double norm() {
        return sqrt(x * x + y * y);
    }
};

int cmp(double x) {
    if(x > 1e-9)
        return 1;
    if(x < 1e-9)
        return -1;
    return 0;
}

double dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}

double det(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}

double dist(Point a, Point b) {
    return (a - b).norm();
}


double dis_point_segment(const Point p, const Point s, const Point t) {
    if(cmp(dot(p - s, t - s)) < 0)
        return (p - s).norm();
    if(cmp(dot(p - t, s - t)) < 0)
        return (p - t).norm();
    return fabs(det(s - p, t - p)) / dist(s, t);
}

void test_case() {
    int n;
    double X, Y;
    scanf("%d%lf%lf", &n, &X, &Y);
    double R = 0, r = 1e18;
    for(int i = 1; i <= n; ++i) {
        scanf("%lf%lf", &x[i], &y[i]);
        R = max(R, (X - x[i]) * (X - x[i]) + (Y - y[i]) * (Y - y[i]));
    }
    R = sqrt(R);
    Point O(X, Y);
    for(int i = 2; i <= n; ++i)
        r = min(r, dis_point_segment(O, Point(x[i], y[i]), Point(x[i - 1], y[i - 1])));
    r = min(r, dis_point_segment(O, Point(x[1], y[1]), Point(x[n], y[n])));
    printf("%.12f\n", (R * R - r * r)* acos(-1.0));
}

Codeforces Round #338 (Div. 2)

原文：https://www.cnblogs.com/KisekiPurin2019/p/12264559.html