ഇത് സ്‌ട്രെയിറ്റ് ലൈൻ ലീറ്റ്‌കോഡ് പരിഹാരമാണോയെന്ന് പരിശോധിക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു പാലന്തിർ ടെക്നോളജീസ്
അറേ മഠം

ഈ പ്രശ്‌നത്തിൽ, ഞങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് ശ്രേണി പോയിന്റുകളുടെ. ഇത് ഒരു 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) , പി 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 രണ്ടാമത്തെ പോയിന്റിന്റെ y- കോർഡിനേറ്റായി. സമാനമായി, (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

ഇത് ഒരു സ്‌ട്രെയിറ്റ് ലൈൻ ലീറ്റ്‌കോഡ് പരിഹാരമാണെങ്കിൽ ചെക്കിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N) ഇവിടെ N = അറേയിലെ പോയിന്റുകളുടെ എണ്ണം. ഞങ്ങൾ അറേയുടെ ഒരൊറ്റ പാസ് ചെയ്യുന്നു, അതിൽ ചെയ്യുന്ന എല്ലാ പ്രവർത്തനങ്ങൾക്കും സ്ഥിരമായ സമയമെടുക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1) ഞങ്ങൾ സ്ഥിരമായ മെമ്മറി ഇടം മാത്രമേ ഉപയോഗിക്കുന്നുള്ളൂ.