এটি কিনা স্ট্রেট লাইন লেটকোড সমাধান কিনা তা পরীক্ষা করে দেখুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় পালান্টিয়ার টেকনোলজিস
বিন্যাস ম্যাথ

এই সমস্যায়, আমাদের একটি দেওয়া হয় বিন্যাস পয়েন্ট। এটি এক্স-কোঅর্ডিনেট এবং কিছু পয়েন্টের ওয়াই-কোঅর্ডিনেটের একটি তালিকা প্রতিনিধিত্ব করে যা একটি এক্সওয়াই 2-ডি বিমানে অবস্থিত। আমাদের এই পয়েন্টগুলি একটি সরলরেখা তৈরি করে কিনা তা খতিয়ে দেখা দরকার। নোট করুন যে ইনপুটটিতে কমপক্ষে 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).

এখন, পি 1 এবং পি 2 এর মধ্য দিয়ে যেতে একটি লাইন তৈরি করুন। এই লাইনের opeাল হবে:

ঢাল = (y2 - y1) / (x2 - x1)

P3 P1 এবং P2 এর সাথে সমান্তরাল তা নিশ্চিত করার জন্য, আসুন প্রথমে P2 এবং P3 পয়েন্ট দ্বারা গঠিত রেখার findালু সন্ধান করি। এটাই,

ঢাল(পি 2 এবং পি 3) = (y3 - y2) / (x3 - x2)

এখন, পয়েন্টগুলি কেবলমাত্র এবং কেবলমাত্র: P1 এবং P2 দ্বারা গঠিত রেখার opeাল = P2 এবং P3 দ্বারা গঠিত লাইনের opeালু।

সুতরাং, পি 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) সমান Opeাল (1, i) দ্বারা আমরা উপরে দেখেছি হিসাবে ক্রস পণ্য চেক.

অ্যালগরিদম

  1. আমরা একটি বুলিয়ান ফাংশন ব্যবহার করি চেকস্প্রাইটলাইন () বিন্দুগুলির একটি অ্যারে এটি সরানো একটি সরলরেখা তৈরি করে কিনা তা ফেরত দিতে
  2. যদি অ্যারেটি কেবল থাকে 2 পয়েন্ট:
    • সত্য ফিরে
  3. আরম্ভ x0 প্রথম পয়েন্টের এক্স-সমন্বয় হিসাবে এবং y0 দ্বিতীয় দফার y- সমন্বয় হিসাবে। একইভাবে, (এক্স 1, ওয়াই 1) দ্বিতীয় দফার স্থানাঙ্কের জন্য
  4. যেহেতু ক্রস-প্রোডাক্ট চেকের জন্য আমাদের তাদের পার্থক্য প্রয়োজন, তাই তাদের পার্থক্যগুলি এইভাবে সংরক্ষণ করুন:
    • dx = x1 - x0
    • dy = y1 - y0
  5. দ্বিতীয় বিন্দুর পরে অ্যারেতে প্রতিটি পয়েন্টের জন্য এখন:
    1. এই পয়েন্টের এক্স এবং y স্থানাঙ্কগুলি ভেরিয়েবলগুলিতে সঞ্চয় করুন x এবং y
    2. এখন, আমরা প্রথম দুটি পয়েন্টের opালু এবং এটির এবং প্রথম পয়েন্টের opeালু একই কিনা তা পরীক্ষা করে দেখছি:
      • 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 = পয়েন্টের সংখ্যা। আমরা অ্যারের একক পাস করি এবং এতে সঞ্চালিত সমস্ত ক্রিয়াকলাপ ধ্রুব সময় নেয়।

স্পেস জটিলতা ity

ও (1) যেহেতু আমরা কেবল ধ্রুবক মেমরি স্পেস ব্যবহার করি।