Submission #61818360

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1e9 + 5;
const ll llINF = 1e18;
const int SZ = 1 << 18;
const int mxn = 2e5 + 5;
double dy[] = {0.5, 0.5, -0.5, -0.5};
double dx[] = {0.5, -0.5, 0.5, -0.5};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using pll = pair<ll, ll>;

const int INF = 1e9 + 5;
const ll llINF = 1e18;
const int SZ = 1 << 18;
const int mxn = 2e5 + 5;

double dy[] = {0.5, 0.5, -0.5, -0.5};
double dx[] = {0.5, -0.5, 0.5, -0.5};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll R;
    cin >> R;

    ll ans = 0;

    // 원 R이 있는 곳이 원점이고
    // R안에 들어오려면 모든 사각형의 꼭짓점이 원의 넓이 안에 존재해야한다.

    for(int i = -R; i <= R; i++) {
        // for(int j = -R; j <= R; j++) {
        //     bool ok = true;
        //     for(int k = 0; k < 4; k++) {
        //         double a = (double)i + dx[k];
        //         double b = (double)j + dy[k];
        //         if (a*a + b*b > R*R) {
        //             ok = false;
        //             break;
        //         }
        //     }
        //     if(ok) {
        //         ans++;
        //     }
        // }

        int lo = -R;
        int hi = 0;

        while(lo <= hi) {
            int mid = (lo + hi) / 2;
            bool ok = true;
            for(int k = 0; k < 4; k++) {
                double a = (double)i + dx[k];
                double b = (double)mid + dy[k];
                if (a*a + b*b > R*R) {
                    ok = false;
                    break;
                }
            }

            // 포함이 되면?
            if(ok) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        int lo2 = 1;
        int hi2 = R;

        while(lo2 <= hi2) {
            int mid = (lo2 + hi2) / 2;
            // 포함이 되면?
            bool ok = true;
            for(int k = 0; k < 4; k++) {
                double a = (double)i + dx[k];
                double b = (double)mid + dy[k];
                if (a*a + b*b > R*R) {
                    ok = false;
                    break;
                }
            }

            // 반대로 포함이 되면 상한을 높여야함
            if(ok) {
                lo2 = mid + 1;
            } else {
                hi2 = mid - 1;
            }
        }

        ans += (lo2 - lo);
    }

    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result