ಇದು ಸ್ಟ್ರೈಟ್ ಲೈನ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಪಲಂತಿರ್ ಟೆಕ್ನಾಲಜೀಸ್
ಅರೇ ಮಠ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಒಂದು ನೀಡಲಾಗಿದೆ ಸರಣಿ ಅಂಕಗಳ. ಇದು 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

ವಿವರಣೆ: ಸಂಪರ್ಕಿತ ಎರಡು ಬಿಂದುಗಳು ಯಾವಾಗಲೂ ಸರಳ ರೇಖೆಯನ್ನು ರೂಪಿಸುತ್ತವೆ.

ಅಪ್ರೋಚ್

ಕೊಟ್ಟಿರುವ ಪಟ್ಟಿಯಲ್ಲಿ ಕೇವಲ ಎರಡು ಅಂಶಗಳಿದ್ದರೆ ಅವು ಯಾವಾಗಲೂ ಸರಳ ರೇಖೆಯನ್ನು ರೂಪಿಸುತ್ತವೆ ಮತ್ತು ಫಲಿತಾಂಶವು ನಿಜವಾಗುತ್ತದೆ ಎಂದು ಗಮನಿಸುವುದು ಸುಲಭ. ಆದಾಗ್ಯೂ, ಮೂರು ಅಂಶಗಳಿದ್ದರೆ, ಅವೆಲ್ಲವೂ ಕೊಲೈನಿಯರ್ ಆಗಿರಬಹುದು ಅಥವಾ ಇರಬಹುದು. ಆದ್ದರಿಂದ, ನಾವು ಯಾವುದೇ ಎರಡು ಬಿಂದುಗಳನ್ನು ಸರಿಪಡಿಸಬಹುದು, ಅವುಗಳ ಮೂಲಕ ಹಾದುಹೋಗುವ ರೇಖೆಯನ್ನು ರೂಪಿಸಬಹುದು ಮತ್ತು ಉಳಿದ ಎಲ್ಲಾ ಬಿಂದುಗಳು ಒಂದೇ ಸಾಲಿನಲ್ಲಿ ಇದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಬಹುದು. ಗಣಿತದ ಪ್ರಕಾರ, ಇದನ್ನು ಪರಿಶೀಲಿಸುವ ಮೂಲಕ ಮಾಡಬಹುದು ಇಳಿಜಾರು ಯಾವುದೇ ಎರಡು ಬಿಂದುಗಳ ನಡುವೆ ರೂಪುಗೊಂಡ ರೇಖೆಯ. ಉದಾಹರಣೆಗೆ, ನಮಗೆ ಮೂರು ಅಂಶಗಳಿವೆ ಎಂದು ಪರಿಗಣಿಸೋಣ: ಪಿ 1 = (x1, y1) , ಪಿ 2 = (x2, y2) ಮತ್ತು ಪಿ 3 = (x3, y3).

ಈಗ, ಪಿ 1 ಮತ್ತು ಪಿ 2 ಮೂಲಕ ಹಾದುಹೋಗುವ ರೇಖೆಯನ್ನು ರೂಪಿಸೋಣ. ಈ ಸಾಲಿನ ಇಳಿಜಾರು ಹೀಗಿರುತ್ತದೆ:

ಇಳಿಜಾರು = (y2 - y1) / (x2 - x1)

ಪಿ 3 ಪಿ 1 ಮತ್ತು ಪಿ 2 ನೊಂದಿಗೆ ಕೊಲೈನಿಯರ್ ಆಗಿದೆಯೆ ಎಂದು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು, ಮೊದಲು ಪಿ 2 ಮತ್ತು ಪಿ 3 ಬಿಂದುಗಳಿಂದ ರೂಪುಗೊಂಡ ರೇಖೆಯ ಇಳಿಜಾರನ್ನು ಕಂಡುಹಿಡಿಯೋಣ. ಅದು,

ಇಳಿಜಾರು(ಪಿ 2 ಮತ್ತು ಪಿ 3) = (y3 - y2) / (x3 - x2)

ಈಗ, ಬಿಂದುಗಳು ಕೊಲಿನೀಯರ್ ಆಗಿದ್ದರೆ ಮತ್ತು ಹೀಗಿದ್ದರೆ ಮಾತ್ರ: ಪಿ 1 ಮತ್ತು ಪಿ 2 ನಿಂದ ರೂಪುಗೊಂಡ ರೇಖೆಯ ಇಳಿಜಾರು = ಪಿ 2 ಮತ್ತು ಪಿ 3 ನಿಂದ ರೂಪುಗೊಂಡ ರೇಖೆಯ ಇಳಿಜಾರು.

ಆದ್ದರಿಂದ, ಪಿ 1, ಪಿ 2 ಮತ್ತು ಪಿ 3 ಕೊಲೈನಿಯರ್ ಆಗಿದ್ದರೆ, ನಾವು ಹೊಂದಿದ್ದೇವೆ

(y2 - y1): (x2 - x1) :: (y3 - y2): (x3 - x2), ಅಥವಾ

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

ಆದ್ದರಿಂದ, ನಾವು ಎರಡು ಅಂಕಗಳನ್ನು ಸರಿಪಡಿಸಬಹುದು, ಪಿ 1 ಮತ್ತು ಪಿ 2 ಎಂದು ಹೇಳಿ ಮತ್ತು ಪ್ರತಿಯೊಂದಕ್ಕೂ i > 2 ಇನ್ಪುಟ್ ಪಟ್ಟಿಯಲ್ಲಿ, ನಾವು ಪರಿಶೀಲಿಸಬಹುದು ಇಳಿಜಾರು (1, 2) ಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ ಇಳಿಜಾರು (1, i) ಇವರಿಂದ ನಾವು ಮೇಲೆ ನೋಡಿದಂತೆ ಅಡ್ಡ-ಉತ್ಪನ್ನ ಪರಿಶೀಲನೆ.

ಕ್ರಮಾವಳಿ

  1. ನಾವು ಬೂಲಿಯನ್ ಕಾರ್ಯವನ್ನು ಬಳಸುತ್ತೇವೆ checkStraightLine () ಅದಕ್ಕೆ ರವಾನಿಸಲಾದ ಬಿಂದುಗಳ ಒಂದು ಶ್ರೇಣಿಯು ನೇರ ರೇಖೆಯನ್ನು ರೂಪಿಸುತ್ತದೆಯೇ ಎಂದು ಹಿಂತಿರುಗಿಸಲು
  2. ರಚನೆಯು ಮಾತ್ರ ಹೊಂದಿದ್ದರೆ 2 ಅಂಕಗಳು:
    • ನಿಜ ಹಿಂತಿರುಗಿ
  3. ಪ್ರಾರಂಭಿಸಿ x0 ಮೊದಲ ಬಿಂದುವಿನ x- ನಿರ್ದೇಶಾಂಕವಾಗಿ ಮತ್ತು y0 ಎರಡನೇ ಬಿಂದುವಿನ ವೈ-ನಿರ್ದೇಶಾಂಕದಂತೆ. ಅಂತೆಯೇ, (x1, y1) ಎರಡನೇ ಬಿಂದುವಿನ ನಿರ್ದೇಶಾಂಕಗಳಿಗಾಗಿ
  4. ಅಡ್ಡ-ಉತ್ಪನ್ನ ಪರಿಶೀಲನೆಗಾಗಿ ನಮಗೆ ಅವುಗಳ ವ್ಯತ್ಯಾಸ ಬೇಕಾಗಿರುವುದರಿಂದ, ಅವರ ವ್ಯತ್ಯಾಸಗಳನ್ನು ಹೀಗೆ ಸಂಗ್ರಹಿಸಿ:
    • dx = x1 - x0
    • dy = y1 - y0
  5. ಈಗ ಎರಡನೇ ಹಂತದ ನಂತರ ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಬಿಂದುವಿಗೂ:
    1. ಈ ಬಿಂದುವಿನ x ಮತ್ತು y ನಿರ್ದೇಶಾಂಕಗಳನ್ನು ಅಸ್ಥಿರಗಳಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ x ಮತ್ತು y
    2. ಈಗ, ಮೊದಲ ಎರಡು ಬಿಂದುಗಳ ಇಳಿಜಾರು ಮತ್ತು ಇದರ ಇಳಿಜಾರು ಮತ್ತು ಮೊದಲ ಬಿಂದು ಒಂದೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ:
      • If dy * (x - x0) is ಅಲ್ಲ ಸಮಾನವಾಗಿರುತ್ತದೆ dx * (y - y0)
        • ಸುಳ್ಳನ್ನು ಹಿಂತಿರುಗಿ
  6. ನಿಜ ಹಿಂತಿರುಗಿ
  7. ಫಲಿತಾಂಶವನ್ನು ಮುದ್ರಿಸಿ

ಇದು ನೇರ ರೇಖೆಯ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವಾಗಿದ್ದರೆ ಚೆಕ್ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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

ಇದು ನೇರ ರೇಖೆಯ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವಾಗಿದ್ದರೆ ಚೆಕ್‌ನ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್) ಅಲ್ಲಿ N = ಶ್ರೇಣಿಯಲ್ಲಿನ ಬಿಂದುಗಳ ಸಂಖ್ಯೆ. ನಾವು ರಚನೆಯ ಒಂದೇ ಪಾಸ್ ಅನ್ನು ಮಾಡುತ್ತೇವೆ ಮತ್ತು ಅದರಲ್ಲಿ ನಿರ್ವಹಿಸಲಾದ ಎಲ್ಲಾ ಕಾರ್ಯಾಚರಣೆಗಳು ಸ್ಥಿರ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1) ನಾವು ಸ್ಥಿರವಾದ ಮೆಮೊರಿ ಸ್ಥಳವನ್ನು ಮಾತ್ರ ಬಳಸುತ್ತೇವೆ.