22.6 แบบฝึกหัด

เขียนแต่ละข้อเป็นไฟล์ใหม่ใน Code::Blocks รันแล้วเทียบกับผลลัพธ์ที่ต้องได้ให้ตรงทุกตัวอักษร รวมถึงช่องว่างและการขึ้นบรรทัด ติดจริงๆ ค่อยเปิดคำใบ้ และเปิดเฉลยหลังทำเสร็จแล้วเท่านั้น

ข้อ 1 รวมคะแนนสองห้อง

ระดับง่าย เวลาไม่เกิน 1 วินาที

ครูประจำชั้นสองห้องส่งคะแนนสอบกลางภาคมาให้ฝ่ายวิชาการ ห้อง A มีนักเรียน N คน ห้อง B มี M คน แต่ละห้องเรียงคะแนนจากน้อยไปมากมาแล้ว ฝ่ายวิชาการต้องการรายการคะแนนของทั้งสองห้องรวมกัน เรียงจากน้อยไปมาก เพื่อนำไปหาเกณฑ์ตัดเกรดของทั้งระดับชั้น

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 1 ≤ N, M ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือคะแนนของห้อง A เรียงจากน้อยไปมาก (อาจมีค่าซ้ำ)

บรรทัดที่สามมีจำนวนเต็ม M ตัว คือคะแนนของห้อง B เรียงจากน้อยไปมาก (อาจมีค่าซ้ำ)

คะแนนทุกค่าอยู่ระหว่าง 0 ถึง 10⁹

ข้อมูลออก

บรรทัดเดียว มีคะแนนทั้งหมด N + M ค่าเรียงจากน้อยไปมาก คั่นด้วยช่องว่างหนึ่งช่อง

4 5
35 52 70 88
40 41 66 90 95

35 40 41 52 66 70 88 90 95

3 2
10 20 30
40 50

10 20 30 40 50

ดูคำใบ้

นี่คือขั้นรวมของ merge sort ในหน้า 22.2 ใช้สองตัวชี้ ตัวละห้อง เทียบคะแนนที่ตัวชี้ทั้งสองชี้อยู่ หยิบตัวที่น้อยกว่าใส่ผลลัพธ์แล้วเลื่อนตัวชี้นั้น พอห้องใดหมด อย่าลืมเทคะแนนที่เหลือของอีกห้องต่อท้ายให้ครบ ทั้งหมดเป็น O(N + M) ลองกับห้องที่คะแนนทุกคนมากกว่าทุกคนในอีกห้องด้วย

ดูเฉลย

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> room_a(n), room_b(m);
    for (int i = 0; i < n; i++) {
        cin >> room_a[i];
    }
    for (int j = 0; j < m; j++) {
        cin >> room_b[j];
    }
    vector<int> merged;
    merged.reserve(n + m);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (room_a[i] <= room_b[j]) {
            merged.push_back(room_a[i]);
            i++;
        } else {
            merged.push_back(room_b[j]);
            j++;
        }
    }
    while (i < n) {
        merged.push_back(room_a[i]);
        i++;
    }
    while (j < m) {
        merged.push_back(room_b[j]);
        j++;
    }
    for (int k = 0; k < n + m; k++) {
        cout << merged[k] << (k == n + m - 1 ? '\n' : ' ');
    }
    return 0;
}

ข้อ 2 ซื้อของ K ชิ้นที่ถูกที่สุด

ระดับง่าย เวลาไม่เกิน 1 วินาที

ชมรมวิทยาศาสตร์ได้งบซื้ออุปกรณ์ทดลอง ร้านมีอุปกรณ์ที่ใช้ได้ N ชิ้น ชิ้นที่ i ราคา p_i บาท ชมรมต้องซื้อ K ชิ้นพอดี และเลือกชิ้นไหนก็ได้ จึงซื้อ K ชิ้นที่ถูกที่สุด ให้หาว่าต้องจ่ายรวมกี่บาท

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ K คั่นด้วยช่องว่าง โดยที่ 1 ≤ K ≤ N ≤ 500000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ p₁ ถึง p_N โดยที่ 1 ≤ p_i ≤ 10⁹

ข้อมูลออก

ราคารวมของ K ชิ้นที่ถูกที่สุด

6 3
120 45 300 45 80 999

ดูคำใบ้

ถ้าหาชิ้นที่ถูกที่สุดทีละรอบแบบ selection sort ในหน้า 13.2 ต้องไล่ทั้งร้าน K รอบ เป็น O(NK) ซึ่งถึงราว 10¹¹ เมื่อ K เป็นครึ่งหนึ่งของห้าแสน ใช้ nth_element ในหน้า 22.4 ให้ชิ้นที่ถูกเป็นอันดับ K ไปอยู่ช่อง K - 1 แล้ว K ช่องแรกจะเป็น K ชิ้นที่ถูกที่สุดพอดี แม้ข้างในยังไม่เรียง บวกได้เลย เป็น O(N) เฉลี่ย หรือจะ sort ทั้งร้านก่อนแบบ O(N log N) ก็ทันเหมือนกัน ราคารวมเกิน int ได้

ดูเฉลย

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> price(n);
    for (int i = 0; i < n; i++) {
        cin >> price[i];
    }
    nth_element(price.begin(), price.begin() + (k - 1), price.end());
    long long total = 0;
    for (int i = 0; i < k; i++) {
        total += price[i];
    }
    cout << total << '\n';
    return 0;
}

ข้อ 3 สลับแถวหน้าเสาธง

ระดับง่าย เวลาไม่เกิน 1 วินาที

นักเรียน N คนยืนเข้าแถวหน้าเสาธง คนที่ i จากหัวแถวสูง h_i เซนติเมตร ครูอยากให้แถวเรียงจากเตี้ยไปสูง จึงให้นักเรียนสองคนที่ยืนติดกันสลับที่กันได้ทีละคู่ โดยสลับเฉพาะคู่ที่คนหน้าสูงกว่าคนหลังเท่านั้น คนที่สูงเท่ากันไม่ต้องสลับกัน ให้หาว่าต้องสลับทั้งหมดกี่ครั้งแถวจึงจะเรียง

จำนวนครั้งที่ต้องสลับไม่ขึ้นกับว่าสลับคู่ไหนก่อน และเท่ากับจำนวนคู่ i < j ที่ h_i > h_j

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ h₁ ถึง h_N โดยที่ 1 ≤ h_i ≤ 10⁹

ข้อมูลออก

จำนวนครั้งที่ต้องสลับ

5
150 160 155 145 158

4
140 140 135 140

ดูคำใบ้

จำนวนครั้งที่สลับคือจำนวนคู่ที่ผิดลำดับตามหน้า 13.3 ลองทุกคู่เป็น O(N²) ราว 2 × 10¹⁰ คู่ ไม่ทัน ใช้ merge sort นับคู่สลับในหน้า 22.3 ตอนรวมสองครึ่ง ทุกครั้งที่หยิบจากครึ่งขวาก่อน ให้บวกจำนวนตัวที่เหลือในครึ่งซ้าย คนสูงเท่ากันต้องหยิบจากครึ่งซ้ายก่อน (ใช้ <=) และคำตอบถึงราว 2 × 10¹⁰ ต้องเป็น long long

ดูเฉลย

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

long long count_swaps(vector<int> &height, vector<int> &temp, int lo, int hi)
{
    if (hi - lo <= 1) {
        return 0;
    }
    int mid = (lo + hi) / 2;
    long long swaps = count_swaps(height, temp, lo, mid) + count_swaps(height, temp, mid, hi);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (height[i] <= height[j]) {
            temp[k] = height[i];
            i++;
        } else {
            temp[k] = height[j];
            j++;
            swaps += mid - i;
        }
        k++;
    }
    while (i < mid) {
        temp[k] = height[i];
        i++;
        k++;
    }
    while (j < hi) {
        temp[k] = height[j];
        j++;
        k++;
    }
    for (int t = lo; t < hi; t++) {
        height[t] = temp[t];
    }
    return swaps;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> height(n);
    for (int i = 0; i < n; i++) {
        cin >> height[i];
    }
    vector<int> temp(n);
    cout << count_swaps(height, temp, 0, n) << '\n';
    return 0;
}

ข้อ 4 ลายพับกระดาษ

ระดับกลาง เวลาไม่เกิน 1 วินาที

น้องเอากระดาษแถบยาวมาพับครึ่ง โดยยกปลายขวาทับไปบนปลายซ้ายทุกครั้ง แล้วพับครึ่งแบบเดิมซ้ำจนครบ k ครั้ง พอคลี่ออกจะเห็นรอยพับ 2^k - 1 รอยเรียงจากซ้ายไปขวา แต่ละรอยเป็นรอยพับลงแบบหุบเขา (V) หรือรอยพับขึ้นแบบสันเขา (M) ลายของรอยพับเป็นไปตามกฎนี้

พับครั้งเดียว ได้ลาย V
ลายของการพับ k ครั้ง คือลายของการพับ k - 1 ครั้ง ต่อด้วยรอย V หนึ่งรอยตรงกลาง แล้วต่อด้วยลายของการพับ k - 1 ครั้งที่ กลับลำดับจากขวาไปซ้าย และสลับ V กับ M ทุกตัว

เช่น พับ 2 ครั้งได้ VVM พับ 3 ครั้งได้ VVMVVMM เมื่อพับหลายสิบครั้ง (ซึ่งทำไม่ได้กับกระดาษจริง แต่คำนวณได้) ลายจะยาวมากจนเขียนออกมาทั้งเส้นไม่ไหว ให้ตอบว่ารอยพับที่ตำแหน่ง p จากซ้ายเป็น V หรือ M

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม k และ Q คั่นด้วยช่องว่าง โดยที่ 1 ≤ k ≤ 60 และ 1 ≤ Q ≤ 100000

อีก Q บรรทัด บรรทัดละหนึ่งคำถาม มีจำนวนเต็ม p โดยที่ 1 ≤ p ≤ 2^k - 1

ข้อมูลออก

Q บรรทัด ตอบตามลำดับคำถาม บรรทัดละตัวอักษรเดียว คือ V หรือ M

V
V
M
V
V
M
M

M
V
V
M

ดูคำใบ้

ลายของการพับ k ครั้งยาว 2^k - 1 ตัว รอยตรงกลางอยู่ที่ตำแหน่ง m = 2^k-1 ถ้า p = m ตอบ V ถ้า p < m รอยนั้นอยู่ในลายของการพับ k - 1 ครั้งที่ตำแหน่ง p เดิม ถ้า p > m รอยนั้นมาจากลายของการพับ k - 1 ครั้งที่กลับลำดับแล้ว ตำแหน่งในลายเดิมคือ 2^k - p แล้วสลับ V กับ M ทุกกรณีเหลือปัญหาเดียวที่เล็กลง เป็น decrease and conquer แบบ binary search ในหน้า 22.1 ตอบหนึ่งคำถามไม่เกิน k ขั้น ใช้ 1LL << k เพราะ 2⁶⁰ เกิน int

ดูเฉลย

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

char crease(int k, long long p)
{
    long long middle = 1LL << (k - 1);
    if (p == middle) {
        return 'V';
    }
    if (p < middle) {
        return crease(k - 1, p);
    }
    char mirrored = crease(k - 1, (1LL << k) - p);
    return mirrored == 'V' ? 'M' : 'V';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k, q;
    cin >> k >> q;
    for (int i = 0; i < q; i++) {
        long long p;
        cin >> p;
        cout << crease(k, p) << '\n';
    }
    return 0;
}

ข้อ 5 กระปุกออมสินทวีคูณ

ระดับกลาง เวลาไม่เกิน 1 วินาที

น้องตั้งกติกาออมเงินกับตัวเองแบบทวีคูณ วันแรกหยอดกระปุก 1 บาท ทุกวันถัดไปหยอดเป็น a เท่าของวันก่อนหน้า วันที่ 1 จึงหยอด 1 บาท วันที่ 2 หยอด a บาท วันที่ 3 หยอด a² บาท ไปเรื่อยๆ ถ้าทำครบ n วัน ในกระปุกจะมี 1 + a + a² + ... + a^n-1 บาท

ตัวเลขนี้ใหญ่มาก จึงขอแค่เศษจากการหารด้วย m มีคำถามทั้งหมด T ข้อ แต่ละข้อมี a n และ m ของตัวเอง

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม T โดยที่ 1 ≤ T ≤ 100

อีก T บรรทัด บรรทัดละหนึ่งคำถาม มีจำนวนเต็ม a n และ m คั่นด้วยช่องว่าง โดยที่ 1 ≤ a ≤ 10⁹ และ 1 ≤ n ≤ 10¹⁸ และ 1 ≤ m ≤ 10⁹ (m ไม่จำเป็นต้องเป็นจำนวนเฉพาะ)

ข้อมูลออก

T บรรทัด ตอบตามลำดับคำถาม บรรทัดละหนึ่งค่า คือ (1 + a + a² + ... + a^n-1) mod m

15
2
1

ดูคำใบ้

ให้ S(n) คือผลรวม n วันแรก ถ้า n เป็นคู่ ครึ่งหลังคือครึ่งแรกที่คูณด้วย a^n/2 ทุกพจน์ จึงได้ S(n) = S(n/2) × (1 + a^n/2) ถ้า n เป็นคี่ S(n) = S(n - 1) + a^n-1 เป็นการแบ่งครึ่งแบบยกกำลังเร็วในหน้า 12.1 ให้ฟังก์ชันคืนทั้ง S(n) และ aⁿ เป็น pair จะได้ไม่ต้องยกกำลังแยก เรียกตัวเองไม่เกินราว 120 ครั้ง สูตรอนุกรมเรขาคณิตที่หารด้วย a - 1 ใช้ไม่ได้ เพราะ m ไม่ใช่จำนวนเฉพาะ และ a - 1 อาจเป็น 0 ทุกครั้งที่คูณให้ mod ก่อน ค่าไม่เกิน 10⁹ คูณกันจึงไม่เกิน 10¹⁸ พอดีกับ long long

ดูเฉลย

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

long long a, m;

pair<long long, long long> jar(long long n)
{
    if (n == 0) {
        return make_pair(0, 1 % m);
    }
    if (n % 2 == 1) {
        pair<long long, long long> before = jar(n - 1);
        long long total = (before.first + before.second) % m;
        long long power = before.second * a % m;
        return make_pair(total, power);
    }
    pair<long long, long long> half = jar(n / 2);
    long long total = half.first * ((1 + half.second) % m) % m;
    long long power = half.second * half.second % m;
    return make_pair(total, power);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    for (int c = 0; c < t; c++) {
        long long n;
        cin >> a >> n >> m;
        a %= m;
        cout << jar(n).first << '\n';
    }
    return 0;
}

ข้อ 6 ราคาทองร่วงหนัก

ระดับกลาง เวลาไม่เกิน 1 วินาที

น้องจดราคาปิดของทองคำแท่งหนึ่งบาทติดต่อกัน N วัน วันที่ i ราคา a_i บาท น้องอยากรู้ว่าตลาดผันผวนแค่ไหน จึงนับว่ามีกี่คู่วัน i < j ที่ราคาวันหลังต่ำกว่าวันก่อนเกิน D บาท หรือก็คือ a_i - a_j > D วันสองวันไม่จำเป็นต้องติดกัน

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ D คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ 0 ≤ D ≤ 10⁹

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ a₁ ถึง a_N โดยที่ 1 ≤ a_i ≤ 10⁹

ข้อมูลออก

จำนวนคู่วันที่ราคาลดลงเกิน D บาท

6 10
100 85 120 95 70 110

ดูคำใบ้

ถ้า D = 0 ข้อนี้คือนับคู่สลับในหน้า 22.3 ทุกคู่แบ่งเป็นคู่ในครึ่งซ้าย คู่ในครึ่งขวา และคู่ข้ามครึ่ง เหมือนเดิม ต่างกันตรงที่ต้องนับคู่ข้ามครึ่ง ก่อน รวม เพราะเงื่อนไขไม่ใช่การเทียบที่ใช้ตอนรวม ทั้งสองครึ่งเรียงแล้ว ไล่ j ในครึ่งขวาจากน้อยไปมาก แล้วเลื่อนตัวชี้ i ในครึ่งซ้ายข้ามทุกตัวที่ไม่เกิน a_j + D ตัวที่เหลือในครึ่งซ้ายคือตัวที่มากกว่า a_j + D ทั้งหมด ตัวชี้ i เดินไปทางเดียว ชั้นละ O(N) จากนั้นค่อยรวมสองครึ่งตามปกติ จำนวนคู่ถึงราว 2 × 10¹⁰

ดูเฉลย

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

long long drop;

long long count_drops(vector<long long> &price, vector<long long> &temp, int lo, int hi)
{
    if (hi - lo <= 1) {
        return 0;
    }
    int mid = (lo + hi) / 2;
    long long count = count_drops(price, temp, lo, mid) + count_drops(price, temp, mid, hi);
    int i = lo;
    for (int j = mid; j < hi; j++) {
        while (i < mid && price[i] <= price[j] + drop) {
            i++;
        }
        count += mid - i;
    }
    i = lo;
    int j = mid, k = lo;
    while (i < mid && j < hi) {
        if (price[i] <= price[j]) {
            temp[k] = price[i];
            i++;
        } else {
            temp[k] = price[j];
            j++;
        }
        k++;
    }
    while (i < mid) {
        temp[k] = price[i];
        i++;
        k++;
    }
    while (j < hi) {
        temp[k] = price[j];
        j++;
        k++;
    }
    for (int t = lo; t < hi; t++) {
        price[t] = temp[t];
    }
    return count;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n >> drop;
    vector<long long> price(n);
    for (int i = 0; i < n; i++) {
        cin >> price[i];
    }
    vector<long long> temp(n);
    cout << count_drops(price, temp, 0, n) << '\n';
    return 0;
}

ข้อ 7 กำไรอยู่ในเกณฑ์

ระดับยาก เวลาไม่เกิน 1 วินาที

ร้านกาแฟจดกำไรรายวัน N วัน วันที่ขาดทุนจดเป็นค่าติดลบ เจ้าของร้านตั้งเป้าว่ากำไรรวมของช่วงวันติดกันที่ถือว่า "ปกติ" ต้องอยู่ระหว่าง L ถึง R บาท ให้นับว่ามีกี่ช่วงวันติดกันที่กำไรรวมอยู่ในเกณฑ์นี้ ช่วงวันคือคู่ l กับ r ที่ 1 ≤ l ≤ r ≤ N และกำไรรวมคือ a_l + a_l+1 + ... + a_r ช่วงที่ l หรือ r ต่างกันนับเป็นคนละช่วง

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N L และ R คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ -10¹⁵ ≤ L ≤ R ≤ 10¹⁵

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ a₁ ถึง a_N โดยที่ -10⁹ ≤ a_i ≤ 10⁹

ข้อมูลออก

จำนวนช่วงวันที่กำไรรวมอยู่ระหว่าง L ถึง R รวมทั้งสองค่า

8 3 6
3 2 -1 1 5 -5 5 0

ดูคำใบ้

สร้าง prefix ตามหน้า 19.5 ช่วง l ถึง r ใช้ได้เมื่อ L ≤ prefix[r] - prefix[l - 1] ≤ R จึงต้องนับคู่ i < j ใน prefix[0..N] ที่ prefix[j] - R ≤ prefix[i] ≤ prefix[j] - L เป็นช่วงของค่า ไม่ใช่ค่าเดียว วิธีเรียงแล้วค้นในหน้า 19.5 ใช้ตรงๆ ไม่ได้ ทำ merge sort บนอาเรย์ prefix ทั้งหมด N + 1 ช่อง ก่อนรวมสองครึ่ง ไล่ j ในครึ่งขวาจากน้อยไปมาก ใช้สองตัวชี้ในครึ่งซ้ายชี้ขอบล่างกับขอบบนของค่าที่นับได้ ทั้งสองตัวเดินไปทางเดียวเหมือนข้อราคาทอง ระวัง prefix เป็น long long อย่าลืม prefix[0] และคำตอบถึงราว 2 × 10¹⁰

ดูเฉลย

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

long long low, high;

long long count_ranges(vector<long long> &prefix, vector<long long> &temp, int lo, int hi)
{
    if (hi - lo <= 1) {
        return 0;
    }
    int mid = (lo + hi) / 2;
    long long count = count_ranges(prefix, temp, lo, mid) + count_ranges(prefix, temp, mid, hi);
    int from = lo, to = lo;
    for (int j = mid; j < hi; j++) {
        while (from < mid && prefix[from] < prefix[j] - high) {
            from++;
        }
        while (to < mid && prefix[to] <= prefix[j] - low) {
            to++;
        }
        count += to - from;
    }
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (prefix[i] <= prefix[j]) {
            temp[k] = prefix[i];
            i++;
        } else {
            temp[k] = prefix[j];
            j++;
        }
        k++;
    }
    while (i < mid) {
        temp[k] = prefix[i];
        i++;
        k++;
    }
    while (j < hi) {
        temp[k] = prefix[j];
        j++;
        k++;
    }
    for (int t = lo; t < hi; t++) {
        prefix[t] = temp[t];
    }
    return count;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n >> low >> high;
    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long profit;
        cin >> profit;
        prefix[i] = prefix[i - 1] + profit;
    }
    vector<long long> temp(n + 1);
    cout << count_ranges(prefix, temp, 0, n + 1) << '\n';
    return 0;
}

ข้อ 8 เสาสัญญาณใกล้กันที่สุด

ระดับยาก เวลาไม่เกิน 1 วินาที

บริษัทโทรคมนาคมมีเสาสัญญาณ N ต้นบนแผนที่ ต้นที่ i อยู่ที่พิกัด (x_i, y_i) เสาสองต้นที่อยู่ใกล้กันมากจะรบกวนกัน วิศวกรจึงต้องการรู้ระยะห่างของคู่เสาที่อยู่ใกล้กันที่สุด เพื่อไม่ให้มีปัญหาเรื่องทศนิยม ให้ตอบเป็น กำลังสองของระยะทาง คือ (x_i - x_j)² + (y_i - y_j)² ที่น้อยที่สุดในบรรดาทุกคู่ i ≠ j เสาสองต้นอาจอยู่ที่พิกัดเดียวกันได้

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 2 ≤ N ≤ 200000

อีก N บรรทัด บรรทัดที่ i มีจำนวนเต็ม x_i และ y_i คั่นด้วยช่องว่าง โดยที่ -10⁹ ≤ x_i, y_i ≤ 10⁹

ข้อมูลออก

กำลังสองของระยะทางระหว่างคู่เสาที่ใกล้กันที่สุด

ดูคำใบ้

ทำตามหน้า 22.5 เรียงตาม x แบ่งครึ่ง หาคำตอบของแต่ละครึ่งได้ d แล้วดูเฉพาะเสาในแถบที่ห่างจากเส้นแบ่งตามแนว x น้อยกว่า √d เรียงแถบตาม y แล้วเทียบแต่ละต้นกับต้นถัดไปเฉพาะเมื่อผลต่างของ y ยกกำลังสองยังน้อยกว่า d ข้อนี้พิกัดติดลบได้ ผลต่างของพิกัดถึง 2 × 10⁹ เกิน int ตั้งแต่ตอนลบ ต้องเก็บพิกัดเป็น long long ก่อนลบ ระยะกำลังสองถึง 8 × 10¹⁸ ยังพอดีกับ long long ลองทุกคู่ต้องคำนวณราว 2 × 10¹⁰ คู่

ดูเฉลย

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

vector<pair<long long, long long>> towers;

long long dist2(pair<long long, long long> p, pair<long long, long long> q)
{
    long long dx = p.first - q.first;
    long long dy = p.second - q.second;
    return dx * dx + dy * dy;
}

long long closest(int lo, int hi)
{
    long long best = LLONG_MAX;
    if (hi - lo <= 3) {
        for (int i = lo; i < hi; i++) {
            for (int j = i + 1; j < hi; j++) {
                best = min(best, dist2(towers[i], towers[j]));
            }
        }
        return best;
    }
    int mid = (lo + hi) / 2;
    long long mid_x = towers[mid].first;
    best = min(closest(lo, mid), closest(mid, hi));
    vector<pair<long long, long long>> strip;
    for (int i = lo; i < hi; i++) {
        long long dx = towers[i].first - mid_x;
        if (dx * dx < best) {
            strip.push_back(towers[i]);
        }
    }
    sort(strip.begin(), strip.end(), [](pair<long long, long long> p, pair<long long, long long> q) {
        return p.second < q.second;
    });
    for (int i = 0; i < (int)strip.size(); i++) {
        for (int j = i + 1; j < (int)strip.size(); j++) {
            long long dy = strip[j].second - strip[i].second;
            if (dy * dy >= best) {
                break;
            }
            best = min(best, dist2(strip[i], strip[j]));
        }
    }
    return best;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    towers.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> towers[i].first >> towers[i].second;
    }
    sort(towers.begin(), towers.end());
    cout << closest(0, n) << '\n';
    return 0;
}