Dikbucaqlı Fibonacci Spiral#12370

Dikbucaqlı Fibonacci Spiral (Həll təhlili)

Problem Müəllifi:	Andriy Kholod (Connect)
Hazırlayan:	Andriy Kholod (Connect)
Analiz:	Andriy Kholod (Connect)

Fikir

Hər bir spiral yalnız onun başlanğıc nöqtəsi $(x_{i}, y_{i})$ (x_i,y_i) ilə müəyyən edilir. Onunla bağlı hər şey eynidir: eyni istiqamətlər, eyni seqment uzunluqları, eyni bucaqlar.

Yəni, istənilən spiral sadəcə eyni kanonik spiraldır $(x_{i}, y_{i})$ (x_i,y_i) vektoru ilə köçürülmüş.

Buna görə, $n$ fərqli spiralla ayrı-ayrılıqda işləmək əvəzinə, kifayətdir ki:

$(0, 0)$ -dan başlayan bir kanonik spiral quraq;
onun hər bir seqmenti üçün, bu seqmenti sorğu nöqtəsinə köçürən neçə başlanğıc nöqtəsi olduğunu sayaq.

1) Kanonik Spiral

Biz $(0, 0)$ -dan başlayan bir spiral quracağıq.

Onun $i$ -ci seqmentinin dörd istiqamətdən birinə malik olmasını qəbul edək: $[(1, 0), (0, 1), (- 1, 0), (0, - 1)]$ [ (1,0),\ (0,1),\ (-1,0),\ (0,-1) ] və uzunluğu $f_{i}$ f_i.

Kod sadəcə bu polilinənin ilk seqmentlərini simulyasiya edir və saxlayır:

bütün üfüqi və şaquli seqmentlər;
bütün künc nöqtələri.

Hər seqment üçün aşağıdakılar saxlanılır:

onun tipi: üfüqi və ya şaquli;
sabit koordinat;
ikinci koordinat üçün sərhədlər.

2) Niyə yalnız ilk 55 seqment kifayətdir

Bu, əsas bir nöqtədir.

Spiralların başlanğıc nöqtələri: $∣ x_{i} ∣, ∣ y_{i} ∣ \leq 1 0^{9}$ |x_i|, |y_i| \le 10^9 və sorğu nöqtələri: $∣ x ∣, ∣ y ∣ \leq 1 0^{7}$ |x|, |y| \le 10^7

Beləliklə, əgər $(x, y)$ nöqtəsi $(x_{i}, y_{i})$ (x_i,y_i)-dan başlayan bir spiralın üzərindədirsə, kanonik spiraldakı müvafiq nöqtənin koordinatları $(x - x_{i}, y - y_{i})$ (x - x_i,\ y - y_i) yəni, $∣ x - x_{i} ∣ \leq 1.01 \cdot 1 0^{9}, ∣ y - y_{i} ∣ \leq 1.01 \cdot 1 0^{9} .$ |x - x_i| \le 1.01 \cdot 10^9, |y - y_i| \le 1.01 \cdot 10^9.

Kanonik spiraldakı koordinatlar təxminən Fibonacci ədədləri kimi böyüyür. Bir neçə on addımdan sonra, onlar mütləq dəyərdə $1 0^{9}$ 10^9-dan əhəmiyyətli dərəcədə böyük olur. Buna görə, daha sonra heç bir seqment, köçürmədən sonra, hər hansı bir sorğuya düşə biləcək bir nöqtə verə bilməz.

Kod 55 seqmentin ehtiyatını alır ki, bu da kifayət qədərdir.

3) Bir üfüqi seqmentin töhfəsini necə saymaq olar

Kanonik spiraldə bir üfüqi seqment olsun: $y = c, x \in [L, R] .$ y = c, x \in [L,R].

$(s_{x}, s_{y})$ (s_x,s_y) başlanğıc nöqtəsinə köçürüldükdən sonra, bu olacaq: $y = s_{y} + c, x \in [s_{x} + L, s_{x} + R] .$ y = s_y + c, x \in [s_x + L,\ s_x + R].

Sorğu nöqtəsi $(q_{x}, q_{y})$ (q_x,q_y) bu köçürülmüş seqmentin üzərindədir, yalnız və yalnız:

$q_{y} = s_{y} + c$ q_y = s_y + c və $q_x \in [s_x + L,\ s_x + R]. \end{center} Bunu başlanğıc nöqtəsi üzrə şərtlər kimi yenidən yaza bilərik: \begin{center}$ s_y = q_y - c $v ə$ s_x [q_x - R, q_x - L].

Yəni, hər bir üfüqi seqment üçün problem bu sorğuya çevrilir:

Neçə başlanğıc nöqtəsinin $y = q_{y} - c$ y = q_y - c və $x \in [q_{x} - R, q_{x} - L]$ x \in [q_x - R,\ q_x - L] olduğunu sayın.

4) Şaquli seqmentin töhfəsini necə saymaq olar

Eynilə, əgər kanonik seqment şaqulidirsə: $x = c, y \in [L, R],$ x = c, y \in [L,R], onda $(s_{x}, s_{y})$ (s_x,s_y)-ya köçürüldükdən sonra, bu olacaq: $x = s_{x} + c, y \in [s_{y} + L, s_{y} + R] .$ x = s_x + c, y \in [s_y + L,\ s_y + R].

Nöqtə $(q_{x}, q_{y})$ (q_x,q_y) onun üzərindədir, yalnız və yalnız: $s_{x} = q_{x} - c$ s_x = q_x - c və $s_{y} \in [q_{y} - R, q_{y} - L] .$ s_y \in [q_y - R,\ q_y - L].

Yəni, $x = q_{x} - c$ x = q_x - c və $y \in [q_{y} - R, q_{y} - L]$ y \in [q_y - R,\ q_y - L] olan başlanğıc nöqtələrinin sayını saymalıyıq.

5) Belə nöqtələri necə sürətlə saymaq olar

Biz spiralların başlanğıc nöqtələrini: $(x_{i}, y_{i}) .$ (x_i,y_i).

İki massiv qura bilərik:

by_X: $(x_{i}, y_{i})$ (x_i,y_i) cütləri leksik olaraq sıralanmışdır;
by_Y: $(y_{i}, x_{i})$ (y_i,x_i) də sıralanmışdır.

Sonra:

şaquli seqment üçün $x$ -i düzəldirik və bütün $y$ -ləri aralıqda axtarırıq;
üfüqi seqment üçün $y$ -i düzəldirik və bütün $x$ -ləri aralıqda axtarırıq.

Bu iki ikili axtarışla edilir:

lower_bound — uyğun aralığın başlanğıcı;
upper_bound — sonu.

Bu aralıqdakı nöqtələrin sayı cavaba əlavə olunur.

6) Niyə küncləri çıxarmaq lazımdır

Əgər sorğu nöqtəsi spiralın küncündə tam düşərsə, o iki bitişik seqmentə eyni anda aiddir. Onda eyni spiralı iki dəfə sayacağıq:

bir dəfə əvvəlki seqment vasitəsilə;
bir dəfə daha sonra.

Buna görə, bütün seqmentləri saydıqdan sonra, sorğunun kanonik spiralin zirvəsinə düşdüyü spiralların sayını çıxarmaq lazımdır.

Bu ayrıca bir massivlə saxlanıla bilər.

Əgər kanonik spiralin zirvəsinin koordinatları $(c_{x}, c_{y})$ (c_x,c_y)-dirsə, onda sorğu $(q_{x}, q_{y})$ (q_x,q_y) üçün başlanğıc nöqtələrini axtarırıq: $(s_{x}, s_{y}) = (q_{x} - c_{x}, q_{y} - c_{y}) .$ (s_x,s_y) = (q_x - c_x,\ q_y - c_y).

Belə başlanğıclar artıq iki dəfə sayılıb, ona görə də bir dəfə çıxarılmalıdır.

9) Asimptotiklər

Gəlin $K = 55$ K=55 — yaradılan seqmentlərin sayı.

İlkin emal:

başlanğıc nöqtələrinin sıralanması — $O (n lo g n)$ O(n \log n);
kanonik spiralin qurulması — $O (K)$ .

Bir sorğu:

bütün $K$ seqmentlərini keçiririk;
hər biri üçün $O (lo g n)$ O(\log n) ikili axtarışlar edirik;
ayrıca, bütün $K - 1$ K-1 küncləri keçiririk.

Beləliklə, bir sorğu $O (K lo g n)$ O(K \log n)-də işləyir, və $K$ sabit olduğuna görə, bu sadəcə $O (lo g n)$ O(\log n)-dir.

Cəmi: $O (n lo g n + q lo g n) .$ O(n \log n + q \log n).

Həll Kodu

#include <bits/stdc++.h>
#include <random>
// fast_pragmas

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,tune=native")

// fast_pragmas ended

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using namespace std;

#define ull unsigned long long
#define ll long long
#define ld long double
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define yes cout<<"BƏLİ"<<endl
#define no cout<<"XAHŞI"<<endl
#define pb push_back
#define ln log
#define lg log10
#define log log2
#define here cout<<"BURADADIR"<<endl

const ll clasik = 5e5 + 7;
const ll mln = 1e6 + 7;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
const ll block_size = 450;
const ll INF = 1e17;

ll df[clasik];

struct Segment {
    char type;
    ll fixed;
    ll min_val;
    ll max_val;
};

void solve() {
    ll n;
    cin >> n;

    vector<pair<ll, ll>> by_X(n), by_Y(n);

    ll min_x = (ll)2e18, max_x = -(ll)2e18;
    ll min_y = (ll)2e18, max_y = -(ll)2e18;

    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        by_X[i] = {x, y};
        by_Y[i] = {y, x};

        min_x = min(min_x, x);
        max_x = max(max_x, x);
        min_y = min(min_y, y);
        max_y = max(max_y, y);
    }

    sort(by_X.begin(), by_X.end());
    sort(by_Y.begin(), by_Y.end());

    vector<ll> f(60);
    f[1] = 1;
    f[2] = 1;
    for (int i = 3; i <= 55; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }

    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    vector<Segment> segs;
    vector<pair<ll, ll>> corners;

    ll cx = 0, cy = 0;

    for (int i = 1; i <= 55; i++) {
        ll nx = cx + f[i] * dx[(i - 1) % 4];
        ll ny = cy + f[i] * dy[(i - 1) % 4];

        if ((i - 1) % 2 == 0) {
            segs.pb({'H', cy, min(cx, nx), max(cx, nx)});
        } else {
            segs.pb({'V', cx, min(cy, ny), max(cy, ny)});
        }

        if (i < 55) {
            corners.pb({nx, ny});
        }

        cx = nx;
        cy = ny;
    }

    ll q;
    cin >> q;

    while (q--) {
        ll qx, qy;
        cin >> qx >> qy;
        ll ans = 0;

        for (auto seg : segs) {
            if (seg.type == 'H') {
                ll py = qy - seg.fixed;
                ll px_min = qx - seg.max_val;
                ll px_max = qx - seg.min_val;

                if (py >= min_y && py <= max_y && px_max >= min_x && px_min <= max_x) {
                    auto it_start = lower_bound(by_Y.begin(), by_Y.end(), make_pair(py, px_min));
                    if (it_start != by_Y.end() && it_start->first == py && it_start->second <= px_max) {
                        auto it_end = upper_bound(it_start, by_Y.end(), make_pair(py, px_max));
                        ans += distance(it_start, it_end);
                    }
                }
            } else {
                ll px = qx - seg.fixed;
                ll py_min = qy - seg.max_val;
                ll py_max = qy - seg.min_val;

                if (px >= min_x && px <= max_x && py_max >= min_y && py_min <= max_y) {
                    auto it_start = lower_bound(by_X.begin(), by_X.end(), make_pair(px, py_min));
                    if (it_start != by_X.end() && it_start->first == px && it_start->second <= py_max) {
                        auto it_end = upper_bound(it_start, by_X.end(), make_pair(px, py_max));
                        ans += distance(it_start, it_end);
                    }
                }
            }
        }

        for (auto c : corners) {
            ll px = qx - c.first;
            ll py = qy - c.second;

            if (px >= min_x && px <= max_x && py >= min_y && py <= max_y) {
                auto it_start = lower_bound(by_X.begin(), by_X.end(), make_pair(px, py));
                if (it_start != by_X.end() && it_start->first == px && it_start->second == py) {
                    auto it_end = upper_bound(it_start, by_X.end(), make_pair(px, py));
                    ans -= distance(it_start, it_end);
                }
            }
        }

        cout << ans << endl;
    }
}

signed main() {

    //freopen("deciding_points_input.txt" , "r" , stdin);
    //freopen("outputA.txt" , "w" , stdout);

    speed;
    int test;
    test = 1;
    //precalc();
    //cin >> test;
    for (int tt = 1; tt <= test; tt++) {
        //cout << "Case #" << tt << ": ";
        solve();
    }

    return 0;
}

C++