የቀጥታ መስመር ሌትኮድ መፍትሔ መሆኑን ያረጋግጡ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ ፓንታሪ ቴክኖሎጂስ
ሰልፍ ሒሳብ

በዚህ ችግር ውስጥ እኛ አንድ ተሰጠን ደርድር የነጥቦች ይህ በ ‹XY 2-D› አውሮፕላን ላይ የተኙ አንዳንድ ነጥቦችን የ x- መጋጠሚያዎች እና የ y- መጋጠሚያዎች ዝርዝርን ይወክላል ፡፡ እነዚህ ነጥቦች ቀጥ ያለ መስመር የሚፈጥሩ መሆናቸውን ማረጋገጥ አለብን ፡፡ በመግቢያው ውስጥ ቢያንስ 2 ነጥቦች እንደሚኖሩ ልብ ይበሉ እና የእነሱ ፍጹም እሴቶች ከ 10 ^ 4 አይበልጡም ፡፡

ለምሳሌ

Co-ordinates = {{1 , 2} , {2 , 3} , {3 , 4} , {4 , 5} , {5 , 6}}
true

ማስረጃ የሚከተለው ንድፍ ሁሉም ነጥቦች ኮሊንደር መሆናቸውን ያረጋግጣል ፡፡

የቀጥታ መስመር ሌትኮድ መፍትሔ መሆኑን ያረጋግጡ

Co-ordinates = {{1 , 2} , {3 , 4}}
true

ማስረጃ: ሁለት የተገናኙ ነጥቦች ሁልጊዜ ቀጥ ያለ መስመር ይመሰርታሉ።

ቀረበ

በተጠቀሰው ዝርዝር ውስጥ ሁለት ነጥቦች ብቻ ካሉ ቀጥ ያለ መስመር እንደሚይዙ እና ውጤቱም እውነት እንደሚሆን መገንዘብ ቀላል ነው ፡፡ ሆኖም ፣ ሶስት ነጥቦች ካሉ ፣ ሁሉም ምናልባት ቀጥታ መስመር ላይሆኑ ይችላሉ ፡፡ ስለዚህ ፣ ማናቸውንም ሁለት ነጥቦችን ማስተካከል ፣ በእነሱ በኩል የሚያልፍ መስመር መመስረት እና ሌሎች ሁሉም ነጥቦች በተመሳሳይ መስመር ላይ የተኙ መሆናቸውን ማረጋገጥ እንችላለን ፡፡ በሂሳብ መሠረት ይህ በመፈተሽ ሊከናወን ይችላል መሬቶች በየትኛውም ሁለት ነጥቦች መካከል የተሠራው መስመር ፡፡ ለምሳሌ ፣ ሶስት ነጥቦችን እንዳለን እንመልከት P1 = (x1 ፣ y1) ፣ P2 = (x2 ፣ y2) እና P3 = (x3 ፣ y3).

አሁን ፣ በ P1 እና P2 በኩል የሚያልፍ መስመር እንፍጠር ፡፡ የዚህ መስመር ቁልቁለት

ዳገት = (y2 - y1) / (x2 - x1)

P3 ከ P1 እና P2 ጋር ተጣጣፊ መሆኑን ለማረጋገጥ በመጀመሪያ ነጥቦችን P2 እና P3 የተፈጠረውን መስመር ቁልቁል እንመልከት ፡፡ ያውና,

ዳገት(P2 እና P3) = (y3 - y2) / (x3 - x2)

አሁን ነጥቦቹ ቀጥታ መስመር ላይ ብቻ እና ብቻ ናቸው-በ P1 እና በ P2 እና በ P2 እና በ P3 የተፈጠረ የመስመር ዝለል

ስለዚህ ፣ P1 ፣ P2 እና P3 collinear ከሆኑ እኛ አለን

(y2 - y1): (x2 - x1) :: (y3 - y2): (x3 - x2), ወይም

(y2 - y1) * (x3 - x2) = (x2 - x1) * (y3 - y2)

ስለዚህ ፣ ሁለት ነጥቦችን ማስተካከል እንችላለን ፣ P1 እና P2 ፣ እና ለእያንዳንዱ i > 2 በግብዓት ዝርዝር ውስጥ ፣ እኛ ከሆነ ማረጋገጥ እንችላለን ተዳፋት (1, 2) እኩል ነው ተዳፋት (1, i) በ ከላይ እንዳየነው የመስቀል-ምርት ቼክ.

አልጎሪዝም

  1. የቦሊን ተግባር እንጠቀማለን የፍተሻ መስመር () ወደ እሱ የተላለፉ በርካታ ነጥቦችን ቀጥታ መስመር ይመሰርቱ እንደሆነ ለመመለስ
  2. ድርድሩ ካለበት ብቻ 2 ነጥቦች
    • ወደ እውነት መመለስ
  3. ያስጀምሩ x0 እንደ መጀመሪያው ነጥብ x- አስተባባሪ እና y0 እንደ ሁለተኛው ነጥብ y-አስተባባሪ ፡፡ በተመሳሳይ ፣ (x1 ፣ y1) ለሁለተኛው ነጥብ መጋጠሚያዎች
  4. እኛ ለተለያዩ ምርቶች ማጣሪያ ልዩነታቸውን ስለምንፈልግ ልዩነቶቻቸውን እንደ:
    • dx = x1 - x0
    • ዳይ = y1 - y0
  5. ከሁለተኛው ነጥብ በኋላ በድርድሩ ውስጥ ለእያንዳንዱ ነጥብ
    1. የዚህን ነጥብ x እና y መጋጠሚያዎች በተለዋዋጮች ውስጥ ያከማቹ xy
    2. አሁን የመጀመሪያዎቹ ሁለት ነጥቦች ተዳፋት እና የዚህ እና የመጀመርያው ነጥብ ቁልቁል ተመሳሳይ መሆናቸውን እናረጋግጣለን ፡፡
      • If ዳይ * (x - x0) is አይደለም እኩል ይሆናል dx * (y - y0)
        • ሐሰት መመለስ
  6. ወደ እውነት ተመለስ
  7. ውጤቱን ያትሙ

የቼክ አተገባበር ቀጥተኛ መስመር ሌትኮድ መፍትሄ ከሆነ

C ++ ፕሮግራም

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

bool checkStraightLine(vector <vector <int> > &coordinates)
{
    if(coordinates.size() == 2)
        return true;

    int x0 = coordinates[0][0] , x1 = coordinates[1][0];
    int y0 = coordinates[0][1] , y1 = coordinates[1][1];

    int dx = x1 - x0 , dy = y1 - y0;
    for(int i = 2 ; i < coordinates.size() ; i++)
    {
        int x = coordinates[i][0] , y = coordinates[i][1];
        if(dy * (x - x0) != dx * (y - y0))
            return false;
    }
    return true;
}

int main()
{
    vector <vector <int> > coordinates = {{1 , 2} , {2 , 3} , {3 , 4} , {4 , 5} , {5 , 6}};
    cout << (checkStraightLine(coordinates) ? "true\n" : "false\n");
}

የጃቫ ፕሮግራም

class check_straight_line
{
    public static void main(String args[])
    {
        int[][] coordinates = {{1 , 2} , {2 , 3} , {3 , 4} , {4 , 5} , {5 , 6}};
        System.out.println(checkStraightLine(coordinates) ? "true" : "false");
    }

    static boolean checkStraightLine(int[][] coordinates)
    {
        if(coordinates.length == 2)
            return true;

        int x0 = coordinates[0][0] , x1 = coordinates[1][0];
        int y0 = coordinates[0][1] , y1 = coordinates[1][1];

        int dx = x1 - x0 , dy = y1 - y0;
        for(int i = 2 ; i < coordinates.length ; i++)
        {
            int x = coordinates[i][0] , y = coordinates[i][1];
            if(dy * (x - x0) != dx * (y - y0))
                return false;
        }
        return true;
    }
}
true

የቀጥታ መስመር Leetcode መፍትሔ ከሆነ የቼክ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) በድርድሩ ውስጥ N = የነጥብ ብዛት። የአቀማመጥ አንድ ነጠላ ማለፊያ እናደርጋለን እና በውስጡ የተከናወኑ ሁሉም ክዋኔዎች የማያቋርጥ ጊዜ ይወስዳል።

የቦታ ውስብስብነት

ኦ (1) እኛ የምንጠቀምበት የማያቋርጥ የማስታወሻ ቦታን ብቻ ስለሆነ ፡፡