#include <iostream>
#include <vector>
#include <list>
#include <string>
using namespace std;
struct Point{
int x;
int y;
Point() : x(-1), y(-1) {}
Point(int a, int b) : x(a), y(b) {}
};
class QuadTree{
Point *point;
Point TopLeft, BottomRight;
vector<QuadTree *> children;
list <Point> AP;
int TL=0,TR=1,BR=2,BL=3;
public:QuadTree(){
point = new Point();
}
QuadTree(int x, int y){
point = new Point(x, y);
}
QuadTree(int x1, int y1, int x2, int y2){
if(x2 < x1 || y2 < y1){
return;
}
point = NULL;
TopLeft = *new Point(x1, y1);
BottomRight = *new Point(x2, y2);
children.assign(20, NULL);
for(int i = TL; i <= BL; i++)
children[i] = new QuadTree();
}
void insert(int x, int y){
Point AreaPoints=*new Point(x,y);
AP.push_back(AreaPoints);
if(x < TopLeft.x || x > BottomRight.x|| y < TopLeft.y || y > BottomRight.y){
return;
}
int midx = (TopLeft.x + BottomRight.x)/2,midy = (TopLeft.y + BottomRight.y)/2;
int pos = -1;
if(x <= midx&&y <= midy){
pos = TL;
}else if(x <= midx&&y > midy){
pos = BL;
}else if(x > midx&&y <= midy){
pos = TR;
}else if(x > midx&&y > midy){
pos = BR;
}
if(children[pos]->point ==NULL){
children[pos]->insert(x, y);
return;
}else if(children[pos]->point->x == -1){
delete children[pos];
children[pos] = new QuadTree(x, y);
return;
}else{
int xx = children[pos]->point->x,yy = children[pos]->point->y;
delete children[pos];
children[pos] = NULL;
if(pos == TL){
children[pos] = new QuadTree(TopLeft.x, TopLeft.y, midx, midy);
}else if(pos == BR){
children[pos] = new QuadTree(midx + 1, midy + 1,BottomRight.x, BottomRight.y);
}else if(pos == TR){
children[pos] = new QuadTree(midx + 1, TopLeft.y,BottomRight.x, midy);
}else{
children[pos] = new QuadTree(TopLeft.x, midy + 1,midx, BottomRight.y);
}
children[pos]->insert(xx, yy);
children[pos]->insert(x, y);
}
}
bool Search(int x, int y){
if(x < TopLeft.x || x > BottomRight.x|| y < TopLeft.y || y > BottomRight.y){
return false;
}
int midx = (TopLeft.x + BottomRight.x)/2,midy = (TopLeft.y + BottomRight.y)/2;
int pos = -1;
if(x <= midx&&y <= midy){
pos = TL;
}else if(x <= midx&&y > midy){
pos = BL;
}else if(x > midx&&y <= midy){
pos = TR;
}else if(x > midx&&y > midy){
pos = BR;
}
if(children[pos]->point == NULL){
return children[pos]->Search(x,y);
}else if(children[pos]->point->x == -1){
return false;
}else{
if(x == children[pos]->point->x && y == children[pos]->point->y)
return true;
}
return false;
}
int Area(int x1,int y1,int x2,int y2){
int counter=0;
for (Point p: AP){
if((p.x>=x1&&p.x<=x2)&&(p.y>=y1&&p.y<=y2)){
counter++;
}
}
return counter;
}
};
int main() {
QuadTree tree(1, 1, 40, 40);
cout<<"WELCOME To QuadTree"<<endl;
string str("");//null
int x=0,y=0,w=0,z=0;
while(str!="Exit"){
cout<<"Please enter your desired command(Insert/Search/Area/Exit)"<<endl;
cin>>str;
if(str=="Insert"){
cin>>x;
cin>>y;
tree.insert(x,y);
}if(str=="Search"){
cin>>w;
cin>>z;
if(tree.Search(w,z)==0){
cout <<"False"<<endl;
}else{
cout <<"True"<<endl;
}
}if(str=="Area"){
cin>>x;
cin>>y;
cin>>w;
cin>>z;
cout << tree.Area(x,y,w,z)<<endl;
}
}
return 0;
} Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}