ในปัญหานี้ เราได้รับ n จุดที่โกหกระนาบ 2 มิติ แต่ละพิกัดคือ (x,y) งานของเราคือการแก้ปัญหาการสืบค้นสองครั้ง สำหรับแต่ละข้อความค้นหา เราได้รับจำนวนเต็ม R เราจำเป็นต้องหาจำนวนจุดที่อยู่ภายในวงกลม โดยใช้จุดศูนย์กลางของวงกลมที่จุดกำเนิดและรัศมี R
คำอธิบายปัญหา
สำหรับแต่ละข้อความค้นหา เราจำเป็นต้องค้นหาจำนวนจุดทั้งหมดจาก n จุดที่อยู่ภายในวงกลม (เช่น ภายในเส้นรอบวง) ของรัศมี R และจุดกำเนิดจุดศูนย์กลาง (0, 0)
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากันดีกว่า
อินพุต
n = 4 2 1 1 2 3 3 -1 0 -2 -2 Query 1: 2
ผลลัพธ์
1
คำอธิบาย − สำหรับคำค้นหาของเรา รัศมีคือ 2 จุด -1 0, อยู่ภายในวงกลม และส่วนอื่นๆ ทั้งหมดอยู่ด้านนอก
สมการทางคณิตศาสตร์ของวงกลมคือ (x2 - x1)2 + (x2 - x1)2 =r2 ดังนั้น สำหรับจุดที่อยู่ในวงกลมที่มีจุดศูนย์กลาง (0,0) จุด (x,y) ต้องเป็นไปตาม x2 + y2 <=r2.
ในการแก้ปัญหานี้ วิธีง่ายๆ คือการสำรวจจุดทั้งหมดสำหรับแต่ละข้อความค้นหาและตรวจสอบว่าอยู่ภายในเส้นรอบวงของวงกลมหรือไม่โดยใช้สูตร
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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) เพราะสำหรับแต่ละแบบสอบถาม เราจะคำนวณค่าของ x2 + y2 สำหรับ n คะแนนทั้งหมด
ดังนั้น โซลูชันที่มีประสิทธิภาพ จะถูกคำนวณล่วงหน้าค่าของ x2 + y2 สำหรับ n คะแนนทั้งหมด และจัดเก็บไว้ในอาร์เรย์ที่ใช้ได้กับทุกคิวรี่ แล้วหาวิธีแก้ปัญหาสำหรับแต่ละคำถาม สำหรับการเพิ่มประสิทธิภาพโปรแกรมเพิ่มเติม เราสามารถจัดเรียงอาร์เรย์แล้วค้นหาองค์ประกอบแรกที่อยู่นอกวงกลม เพื่อปรับปรุงเวลาที่ใช้
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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
