Hisoblash geometriyasining asosiy tarmoqlari

Yana shuni ta'kidlash kerakki, bu texnikaning samaradorligi biz foydalanadigan ma'lumotlar tuzilmalariga bog'liq. Umuman olganda, biz C++ da setdan foydalanishimiz mumkin, lekin ba'zida biz qo'shimcha ma'lumotlarni saqlashni talab qilamiz, shuning uchun biz muvozanatlashgan ikkilik daraxtga o'tamiz.

Misol. Sweep Line algoritmining ishlash tartibi

Harakatlar:

SLH -ga s4 -ni kiriting

Test s4-s3 va s4-s2

N ga e1 ga qo'shing

Sweep Line holati: s0, s1, s2, s4, s3

Navbat: b1,e1, b2, b0, b3, b4

#include

using namespace std;

#define MAX_POINTS 500

typedef complex Point;

Point arr[MAX_POINTS];

double dis[MAX_POINTS][MAX_POINTS];

int getPointsInside(int i, double r, int n) {

vector
> angles;

for (int j = 0; j < n; j++) {

if (i != j && dis[i][j] <= 2*r) {

double B = acos(dis[i][j]/(2*r));

double A = arg(arr[j]-arr[i]);

double alpha = A-B;

double beta = A+B;

angles.push_back(make_pair(alpha, true));

angles.push_back(make_pair(beta, false));

}

}

sort(angles.begin(), angles.end());

int count = 1, res = 1;

vector
>::iterator it;

for (it=angles.begin(); it!=angles.end(); ++it) {

if ((*it).second)

count++;

else

count--;

if (count > res)

res = count;

}

return res;

}

int maxPoints(Point arr[], int n, int r) {

for (int i = 0; i < n-1; i++)

for (int j=i+1; j < n; j++)

dis[i][j] = dis[j][i] = abs(arr[i]-arr[j]);

int ans = 0;

for (int i = 0; i < n; i++)

ans = max(ans, getPointsInside(i, r, n));

return ans;

}

int main() {

Point arr[] = {Point(6.47634, 7.69628), Point(5.16828, 4.79915), Point(6.69533, 6.20378)};

int r = 1;

int n = sizeof(arr)/sizeof(arr[0]);

cout << "The maximum number of points are: " << maxPoints(arr, n, r);

return 0;

}