การสืบค้นจำนวนจุดที่อยู่ภายในวงกลมใน C++

ในปัญหานี้ เราได้รับ n จุดที่อยู่บนระนาบ 2 มิติ โดยแต่ละจุดมีพิกัด (x, y) ภารกิจของเราคือการแก้ปัญหาการสืบค้น (queries) สำหรับแต่ละ query เราจะได้รับจำนวนเต็ม R เราต้องหาจำนวนจุดที่อยู่ภายในวงกลม โดยมีศูนย์กลางอยู่ที่จุดกำเนิด (0, 0) และมีรัศมี R

คำอธิบายปัญหา

สำหรับแต่ละ query เราต้องหาจำนวนจุดทั้งหมดจาก n จุดที่อยู่ภายในวงกลม (คืออยู่ภายในเส้นรอบวง) ที่มีรัศมี R และจุดศูนย์กลางอยู่ที่จุดกำเนิด (0, 0)

ตัวอย่างเพื่อเข้าใจปัญหาให้ดียิ่งขึ้น

อินพุต

n = 4
จุด: (2, 1), (1, 2), (3, 3), (-1, 0), (-2, -2)
Query 1: R = 2

เอาต์พุต

1

คำอธิบาย − สำหรับ query นี้ รัศมีคือ 2 จุด (-1, 0) อยู่ภายในวงกลม ส่วนจุดอื่นๆ อยู่ภายนอก

สมการทางคณิตศาสตร์ของวงกลมคือ (x₂ - x₁)² + (y₂ - y₁)² = r² ดังนั้น สำหรับจุดที่จะอยู่ภายในวงกลมที่มีศูนย์กลางอยู่ที่ (0, 0) จุด (x, y) ต้องทำให้ x² + y² ≤ r²

วิธีแก้ปัญหาแบบง่ายคือการวนลูปตรวจสอบทุกจุดสำหรับแต่ละ query และตรวจสอบว่าจุดนั้นอยู่ภายในเส้นรอบวงของวงกลมหรือไม่ โดยใช้สูตรดังกล่าว

ตัวอย่างโปรแกรม (วิธีแบบง่าย)

#include <iostream>
using namespace std;

int solveQuery(int x[], int y[], int n, int R) {
    int count = 0;
    for(int i = 0; i < n; i++) {
        if(((x[i]*x[i]) + (y[i]*y[i])) <= (R*R))
            count++;
    }
    return count;
}

int main() {
    int x[] = { 2, 1, 3, -1, -2 };
    int y[] = { 1, 2, 3, 0, -2 };
    int n = sizeof(x) / sizeof(x[0]);
    int Q = 2;
    int query[] = {4, 2 };
    for(int i = 0; i < Q; i++)
        cout << "For Query " << (i+1) << ": The number of points that lie inside the circle is " << solveQuery(x, y, n, query[i]) << "\n";
    return 0;
}

เอาต์พุต

For Query 1: The number of points that lie inside the circle is 4
For Query 2: The number of points that lie inside the circle is 1

วิธีแก้ปัญหานี้มีความซับซ้อนด้านเวลา O(n×Q) เนื่องจากสำหรับแต่ละ query เราต้องคำนวณค่า x² + y² สำหรับจุดทั้ง n จุด

วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้น คือการคำนวณค่า x² + y² สำหรับจุดทั้ง n จุดล่วงหน้า (precompute) และเก็บไว้ในอาร์เรย์ ซึ่งสามารถนำไปใช้กับทุก query ได้ จากนั้นจัดเรียงอาร์เรย์นี้ และใช้การค้นหาแบบแบ่งครึ่ง (binary search) เพื่อหาจุดแรกที่อยู่นอกวงกลม ซึ่งจะช่วยลดเวลาการทำงานได้อย่างมาก

ตัวอย่างโปรแกรม (วิธีที่มีประสิทธิภาพ)

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

int solveQuery(int points[], int n, int rad) {
    int l = 0, r = n - 1;
    while ((r - l) > 1) {
        int mid = (l + r) / 2;
        if (points[mid] > (rad * rad))
            r = mid - 1;
        else
            l = mid;
    }
    if ((sqrt(points[l])) > (rad * 1.0))
        return 0;
    else if ((sqrt(points[r])) <= (rad * 1.0))
        return r + 1;
    else
        return l + 1;
}

int main() {
    int n = 5;
    int point[n][2] = { {2, 1}, {1, 2}, {3, 3}, {-1, 0}, {-2, -2} };
    int Q = 2;
    int query[] = {4, 2 };
    int points[n];
    
    // Precomputing Values
    for (int i = 0; i < n; i++)
        points[i] = (point[i][0]*point[i][0]) + (point[i][1]*point[i][1]);
    
    sort(points, points + n);
    
    for(int i = 0; i < Q; i++)
        cout << "For Query " << (i+1) << ": The number of points that lie inside the circle is " 
             << solveQuery(points, n, query[i]) << "\n";
    return 0;
}

เอาต์พุต

For Query 1: The number of points that lie inside the circle is 4
For Query 2: The number of points that lie inside the circle is 1