格子手绢_TinyMind

Description

久城送给维多利加一块苏格兰格子手绢，可是手绢不小心被咖啡弄脏了，久城不得不负起清洗的责任。
手绢的格子可以用二维坐标系来描述，手绢左下角坐标为 \((0,0)\) ，右上角坐标为 \((N,M)\) ，也就是说，手绢上一共有 \(N\times M\) 个格子。咖啡在手绢上形成了一个圆形的污点，圆心位于整点 \((X,Y)\) 处，半径为 \(R\)。久城想知道，有多少个格子被完全污染了，多少个格子被部分污染了。
这里，某个格子被“完全污染”的意思为该格内被污点覆盖面积 \(＝1\) ，被“部分污染”的意思为 \(0＜\) 该格内被污点覆盖面积 \(＜1\) 。

Input

一行 \(5\) 个整数 \(N,M,X,Y,R\)

Output

一行两个整数，由一个空格隔开，表示被完全污染的格子数量和被部分污染的格子数量。

Sample Input

2 2 0 0 2

Sample Output

1 3

数据范围

对于 \(100\%\) 的数据， \(N,M\le 1000000,0\le X\le N,0\le Y\le M,R\le 1000000\).

Solution

可意会不可言传

#include<bits/stdc++.h>
using namespace std;

#define N 1000001
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drp(i, a, b) for (int i = a; i >= b; i--)
#define fech(i, x) for (int i = 0; i < x.size(); i++)
#define ll long long

inline int read() {
    int x = 0, flag = 1; char ch = getchar(); while (!isdigit(ch)) { if (!(ch ^ '-')) flag = -1; ch = getchar(); }
    while (isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); return x * flag;
}

inline void write(int x) {
    if (!x) { puts("0"); return; } if (x < 0) putchar('-'), x = -x;
    char buf[30] = ""; int top = 0; while (x) buf[++top] = x % 10 + '0', x /= 10; while (top) putchar(buf[top--]);
}

ll n, m, X, Y, R, u, d, ans1, ans2;
double l[N], r[N];

int main() {
    scanf("%lld%lld%lld%lld%lld", &n, &m, &X, &Y, &R); u = min(m, Y + R), d = max(0ll, Y - R);
    rep(i, d, u) {
        l[i] = X - sqrt(R * R - (ll)(Y - i) * (Y - i));
        r[i] = min((double)n, (X << 1) - l[i]);
        if (l[i] < 0) l[i] = 0;
    }
    rep(i, d, Y - 1) {
        int l1 = ceil(l[i]), r1 = floor(r[i]); //全包含
        int l2 = floor(l[i + 1]), r2 = ceil(r[i + 1]);
        ans1 += r1 - l1;
        ans2 += l1 - l2 + r2 - r1;
    }
    rep(i, Y, u - 1) {
        int l1 = floor(l[i]), r1 = ceil(r[i]);
        int l2 = ceil(l[i + 1]), r2 = floor(r[i + 1]);
        ans1 += r2 - l2;
        ans2 += l2 - l1 + r1 - r2;
    }
    printf("%lld %lld", ans1, ans2);
    return 0;
}

优质内容筛选与推荐>>
1、技术文章索引
2、《XNA高级编程：Xbox 360和Windows》5-1
3、android 不一样的学习记录
4、深度学习思考1
5、一文读懂深度强化学习算法 A3C （Actor-Critic Algorithm）