Ուռուցիկ կեղեւի ալգորիթմ


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Երկրաչափական Morgan Stanley Samsung

«Ուռուցիկ կեղեւի ալգորիթմ» խնդրում մենք տվել ենք մի քանի կետերի շարք: Ամենափոքր բազմանկյունը, որը կարող է ձևավորվել այն կետերի հետ, որոնք պարունակում են իր ներսում մնացած բոլոր կետերը, կկոչվի նրա ուռուցիկ կորպուս:

Ուռուցիկ կեղեւի ալգորիթմ

Դրան կարելի է հասնել ՝ օգտագործելով Arարվիսի ալգորիթմ.

Ալգորիթմ

  1. Նախաձեռնեք ամենաթեժ կետը ՝ 0:
  2. Հայտարարել ա վեկտոր կետի տիպի արդյունքը
  3. Անցեք կետերի օբյեկտի զանգվածը, մինչև գտնվի ձախ առաջնային կետը
  4. Ավելացրեք այդ կետը արդյունքի վեկտորին
  5. Գտեք հաջորդ կետը "Q" այնպիսին, որ ժամացույցի սլաքի հակառակ ուղղությամբ ամենահեն կետն է բոլոր մյուս կետերից
  6. Սահմանեք p կետը "Q" հաջորդ կրկնության համար:
  7. Շարունակեք ավելացնել մինչդեռ "P" հավասար չէ ձախից:

Նկարագրություն

Ուռուցիկ կորպուսը լուծելու մեր հիմնական գաղափարը կողմնորոշում օգտագործելն է: Մենք պատրաստվում ենք գտնել և սկսել ամենափոքր կամ գուցե ամենացածր X կոորդինատից: Եվ մենք կարող ենք դա վերցնել այնքան ժամանակ, մինչև գտնվեն մեր բոլոր կետերը, որոնցում կարող է կուտակվել որոշ կետերի շարք:

Մենք պատրաստվում ենք փոխանցել օգտագործողի Point կետի օբյեկտի զանգվածի կետերը, որոնք այն արդեն սահմանում ենք ծածկագրի սկզբում: Ամբողջ թիվի կետերի և երկարությունների մեր փաստարկները փոխանցվում են ուռուցիկ կեղևի մեջ ֆունկցիա, որտեղ մենք կհայտարարենք անվանված վեկտորը, որի արդյունքում մենք կպահպանենք մեր արդյունքը:

Այժմ նախաստորագրեք ամենաթեժ կետը մինչև 0: մենք այն սկսելու ենք 0-ից, եթե ստանանք x ամենացածր x կոորդինատը կամ ամենահեռավոր կետը, ապա այն փոխելու ենք:

Այժմ անցեք բոլոր կետերը և պարզեք ամենացածրը: Պահպանեք ձախից դեպի դիրքը "P" և հռչակել մի կետ

Այժմ սկսեք do-while հանգույց, որում առաջին բանը, որ մենք անելու ենք, ավելացնել որպես առաջին կետ որպես արդյունք:

Այժմ մենք պետք է գտնենք ժամացույցի սլաքի ուղղությամբ առավելագույն հակառակ կետը բոլոր մյուս կետերի նկատմամբ, դրա համար մենք պատրաստվում ենք օգտագործել կողմնորոշումը: Դրա համար մենք պատրաստեցինք առանձին ֆունկցիա, որը ստուգում է ՝ արդյոք եռապատկերի կողմնորոշումը 2 է, թե ոչ, եթե պարզվում է, որ այն 2 է, ապա թարմացրեք կետի արժեքը "Q".

Սա պետք է շարունակվի մինչև "P" հավասար չէ ձախից:

Օրինակ

Տրված կետերն են.

{{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}};

ձախակողմյան = 0;

Բոլոր կետերն անցնելուց հետո մեր առաջին ամենացածր x կոորդինատը կլինի (0,3), որը այն կպահի արդյունքում:
Այժմ այն ​​ստուգելու է, թե որից x, y զույգն ունի առավելագույն ժամացույցի սլաքի հակառակ ուղղությամբ, քանի որ այն կտա կողմնորոշումը որպես 2 և կթարմացնի կետի արժեքը "Q".
Airույգը կգտնվի որպես (0,0):
Այժմ պատճենեք կետի արժեքը "Q" վերածվել p- ի `որպես հաջորդ կետ` ժամացույցի սլաքի ուղղությամբ առավելագույն հակառակ կետը կրկին պարզելու համար:
Քանի դեռ p- ի արժեքը հավասար չէ ձախից, մենք կօգտագործենք այս օղակը:
Մեր արդյունքը կլինի. (0,3), (0,0), (3,0), (3,3)

Իրականացման

C ++ ծրագիր ուռուցիկ կեղեւի ալգորիթմի համար

#include <iostream>
using namespace std;
#define INF 10000

struct Point
{
        int x;
        int y;
};

int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);

    if (val == 0)
        return 0;
    return (val > 0) ? 1 : 2;
}

void convexHull(Point points[], int n)
{
    if (n < 3)
        return;
    int next[n];

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

    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;

    int p = l, q;
    do
    {
        q = (p + 1) % n;
        for (int i = 0; i < n; i++)
            if (orientation(points[p], points[i], points[q]) == 2)
                q = i;

        next[p] = q;
        p = q;
    }
    while (p != l);

    for (int i = 0; i < n; i++)
    {
        if (next[i] != -1)
            cout << "(" << points[i].x << ", " << points[i].y << ")\n";
    }
}

int main()
{
    Point points[] = { { 0, 3 }, { 2, 2 }, { 1, 1 }, { 2, 1 }, { 3, 0 },
            { 0, 0 }, { 3, 3 } };
    cout << "The points in the convex hull are: ";
    int n = sizeof(points) / sizeof(points[0]);
    convexHull(points, n);
    return 0;
}
The points in the convex hull are: (0, 3)
(3, 0)
(0, 0)
(3, 3)

Java ծրագիր ուռուցիկ կեղեւի ալգորիթմի համար

import java.util.*;
class Point {

  int x, y;

  Point(int x, int y) {
    this.x = x;
    this.y = y;
  }
}

class ConvexHull{

  public static int OrientationMatch(Point check1, Point check2, Point check3) {

    int val = (check2.y - check1.y) * (check3.x - check2.x) - (check2.x - check1.x) * (check3.y - check2.y);

    if (val == 0)
      return 0;

    return (val > 0) ? 1 : 2;
  }

  public static void convex_hull(Point points[], int lengths) {

    if (lengths<3) return;

    Vector<Point> result = new Vector<Point> ();

    int leftmost = 0;

    for (int i = 1; i<lengths; i++)
      if (points[i].x<points[leftmost].x)
        leftmost = i;

    int p = leftmost, pointq;

    do {

      result.add(points[p]);

      pointq = (p + 1) % lengths;

      for (int i = 0; i<lengths; i++) {
        if (OrientationMatch(points[p], points[i], points[pointq]) == 2) {
          pointq = i;
        }
      }
      p = pointq;
    }

    while (p != leftmost);

    System.out.print("The points in the convex hull are: ");
    for (Point temp: result)
      System.out.println("(" + temp.x + ", " + temp.y + ")");

  }

  public static void main(String[] args) {

    Point points[] = new Point[7];
    points[0] = new Point(0, 3);
    points[1] = new Point(2, 3);
    points[2] = new Point(1, 1);
    points[3] = new Point(2, 1);
    points[4] = new Point(3, 0);
    points[5] = new Point(0, 0);
    points[6] = new Point(3, 3);

    int lengths = points.length;
    convex_hull(points, lengths);
  }
}
The points in the convex hull are: (0, 3)
(0, 0)
(3, 0)
(3, 3)

Բարդության վերլուծություն ուռուցիկ կեղեւի ալգորիթմի համար

Timeամանակի բարդություն

Ո (մ * ն) որտեղ n մուտքային կետերի քանակն է, իսկ m ՝ ելքային կետերի քանակը:

Տիեզերական բարդություն

O (n) որտեղ n - մուտքային կետերի քանակը: Այստեղ մենք օգտագործում ենք N չափի զանգված `հաջորդ արժեքը գտնելու համար:

Մանրամասն