તપાસો કે તે કોઈ સીધી લાઇન લીટકોડ સોલ્યુશન છે


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે પાલાનિર ટેકનોલોજીસ
અરે મઠ

આ સમસ્યામાં, અમને એક આપવામાં આવે છે એરે પોઇન્ટ ઓફ. આ એક્સ-કોઓર્ડિનેટ્સ અને કેટલાક પોઇન્ટના વાય-કોઓર્ડિનેટ્સની સૂચિ રજૂ કરે છે જે XY 2-D પ્લેન પર આવે છે. આપણે એ તપાસવાની જરૂર છે કે શું આ બિંદુઓ સીધી રેખા બનાવે છે. નોંધ લો કે ઇનપુટમાં ઓછામાં ઓછા 2 પોઇન્ટ હશે અને તેના નિશ્ચિત મૂલ્યો 10 ^ 4 કરતાં વધુ નહીં હોય.

ઉદાહરણ

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

સમજૂતી નીચેનો આકૃતિ પુષ્ટિ કરે છે કે બધા બિંદુઓ કોલનેરીયર છે.

તપાસો કે તે કોઈ સીધી લાઇન લીટકોડ સોલ્યુશન છે

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

સમજૂતી: બે કનેક્ટેડ પોઇન્ટ હંમેશાં સીધી લીટી બનાવે છે.

અભિગમ

તે અવલોકન કરવું સરળ છે કે જો આપેલ સૂચિમાં ફક્ત બે મુદ્દાઓ છે તો તે હંમેશાં એક સીધી રેખા બનાવશે અને પરિણામ સાચું આવશે. જો કે, જો ત્યાં ત્રણ મુદ્દાઓ છે, તો તે બધા કોલિનિયર હોઈ શકે છે અથવા નહીં. તેથી, અમે કોઈપણ બે પોઇન્ટ્સને ઠીક કરી શકીએ છીએ, તેમાંથી પસાર થતી લાઇન બનાવી શકીએ છીએ, અને તપાસ કરી શકીએ કે અન્ય તમામ બિંદુઓ સમાન લાઇન પર છે કે નહીં. ગણિતરૂપે, આને ચકાસીને કરી શકાય છે ઢાળ કોઈપણ બે બિંદુઓ વચ્ચેની લાઇનની રચના. ઉદાહરણ તરીકે, ચાલો ધ્યાનમાં લઈએ કે અમારી પાસે ત્રણ મુદ્દા છે: પી 1 = (એક્સ 1, વાય 1) , પી 2 = (એક્સ 2, વાય 2) અને પી 3 = (એક્સ 3, વાય 3).

હવે, ચાલો P1 અને P2 દ્વારા પસાર થતી લાઈન બનાવીએ. આ લાઇનનો opeાળ હશે:

ઢાળ = (વાય 2 - વાય 1) / (એક્સ 2 - એક્સ 1)

ખાતરી કરવા માટે કે પી 3 એ પી 1 અને પી 2 સાથે જોડાયેલું છે, ચાલો પ્રથમ બિંદુઓ પી 2 અને પી 3 દ્વારા રચિત લાઇનનો .ોળાવ શોધીએ. તે જ,

ઢાળ(પી 2 અને પી 3) = (વાય 3 - વાય 2) / (એક્સ 3 - એક્સ 2)

હવે, પોઇન્ટ ફક્ત અને ફક્ત ત્યારે જ: જો P1 અને P2 દ્વારા રચિત lineાળ = P2 અને P3 દ્વારા રચિત લાઇનનો .ાળ.

તેથી, જો પી 1, પી 2 અને પી 3 કોલિનિયર છે, તો અમારી પાસે છે

(y2 - y1): (x2 - x1) :: (y3 - y2): (x3 - x2), અથવા

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

તેથી, આપણે P1 અને P2 કહીએ અને દરેક માટે બે મુદ્દાઓ ઠીક કરી શકીએ i > ઇનપુટ સૂચિમાં 2, અમે ચકાસી શકીએ કે નહીં opeાળ (1, 2) બરાબર છે Slાળ (1, i) દ્વારા આપણે ઉપર જોયું તેમ ક્રોસ-પ્રોડક્ટ તપાસો.

અલ્ગોરિધમ

  1. આપણે બુલિયન ફંક્શનનો ઉપયોગ કરીએ છીએ ચેકસાઇટલાઈન () પાછા જવા માટે કે શું પોઇન્ટ્સની એરે તેને સીધી લાઇન બનાવે છે
  2. જો એરે જ હોય 2 મુદ્દાઓ:
    • સાચું પાછા ફરો
  3. પ્રારંભ કરો x0 પ્રથમ બિંદુના x- સંકલન તરીકે અને y0 બીજા બિંદુના વાય-સંકલન તરીકે. એ જ રીતે (એક્સ 1, વાય 1) બીજા બિંદુના સંકલન માટે
  4. અમને ક્રોસ-પ્રોડક્ટ તપાસ માટે તેમના તફાવતની જરૂર હોવાથી, તેમના તફાવતોને આ રીતે સ્ટોર કરો:
    • dx = x1 - x0
    • dy = y1 - y0
  5. હવે બીજા બિંદુ પછી એરેમાં દરેક બિંદુ માટે:
    1. આ બિંદુના x અને y સંકલનને ચલોમાં સંગ્રહિત કરો x અને y
    2. હવે, આપણે તપાસ કરીએ કે પહેલા બે પોઇન્ટની theોળાવ અને આનો theાળ અને પ્રથમ બિંદુ સમાન છે:
      • If ડીવાય * (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

તપાસની જટિલતા વિશ્લેષણ જો તે સીધી લાઇન લીટકોડ સોલ્યુશન છે

સમય જટિલતા

ઓ (એન) જ્યાં એન = એરેમાંના બિંદુઓની સંખ્યા. અમે એરેનો એક પાસ કરીએ છીએ અને તેમાં કરવામાં આવતી બધી કામગીરી સતત સમય લે છે.

અવકાશ જટિલતા

ઓ (1) કારણ કે આપણે ફક્ત સતત મેમરી સ્પેસનો ઉપયોગ કરીએ છીએ.