ពិនិត្យមើលថាតើវាជាដំណោះស្រាយឡេឡេលេខកូដត្រង់


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ បច្ចេកវិជ្ជា Palantir
អារេ គណិតវិទ្យា

នៅក្នុងបញ្ហានេះយើងត្រូវបានផ្តល់ឱ្យ អារេ នៃចំណុច។ នេះតំណាងឱ្យបញ្ជីកូអរដោនេ x និងកូអរដោនេនៃចំណុចមួយចំនួនដែលស្ថិតនៅលើយន្ដហោះ 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

ការពន្យល់: ចំនុចពីរដែលភ្ជាប់គ្នាតែងតែបង្កើតជាបន្ទាត់ត្រង់។

វិធីសាស្រ្ត

វាងាយស្រួលក្នុងការសង្កេតថាប្រសិនបើមានតែពីរចំណុចនៅក្នុងបញ្ជីដែលបានផ្តល់ឱ្យនោះពួកគេនឹងបង្កើតជាបន្ទាត់ត្រង់ជានិច្ចហើយលទ្ធផលនឹងក្លាយជាការពិត។ ទោះយ៉ាងណាក៏ដោយប្រសិនបើមានបីចំណុចពួកគេទាំងអស់អាចឬមិនមានកូលីនេអ៊ែរ។ អញ្ចឹងយើងអាចកែបានចំនុចពីរបង្កើតជាខ្សែដែលឆ្លងកាត់ពួកគេហើយពិនិត្យមើលថាតើចំនុចផ្សេងទៀតទាំងអស់ស្ថិតនៅលើខ្សែតែមួយ។ តាមលក្ខណៈគណិតវិទ្យានេះអាចធ្វើទៅបានដោយធីកឯកសារ ជម្រាល នៃបន្ទាត់ដែលបានបង្កើតឡើងរវាងចំនុចពីរ។ ឧទាហរណ៍យើងពិចារណាថាយើងមានបីចំណុច៖ P1 = (x១, ១) , P2 = (x១, ១) និង P3 = (x១, ១).

ឥឡូវចូរយើងបង្កើតជាខ្សែដែលឆ្លងកាត់ P1 និង P2 ។ ជម្រាលនៃខ្សែនេះនឹងមានៈ

ជម្រាល = (y2 - y1) / (x2 - x1)

ដើម្បីធានាថា P3 ជាបន្ទាត់កាត់ជាមួយ P1 និង P2 ចូរយើងរកជម្រាលនៃបន្ទាត់ដែលបង្កើតឡើងដោយចំណុច P2 និង P3 ជាមុនសិន។ នោះគឺ

ជម្រាល(P2 និង P3) = (y3 - y2) / (x3 - x2)

ឥឡូវនេះចំនុចគឺមានបន្ទាត់កូរេហើយលុះត្រាតែ: ជម្រាលនៃខ្សែដែលបង្កើតឡើងដោយ P1 និង P2 = ជម្រាលនៃខ្សែដែលបង្កើតឡើងដោយ P2 និង P3 ។

ដូច្ន្រះបើ P1, P2 និង P3 ជាកូលីនេអ៊ែរយើងមន

(y2 - y1): (x2 - x1) :: (y3 - y2): (x៣ - x២) ឬ

(y2 - y1) * (x៣ - x២) = (x២ - x១) * (y៣ - y២)

ដូច្នេះយើងអាចដោះស្រាយបានពីរចំណុចគឺនិយាយថា P1 និង P2 ហើយសម្រាប់រាល់ចំណុចនីមួយៗ i > ២ នៅក្នុងបញ្ជីបញ្ចូលយើងអាចពិនិត្យមើលប្រសិនបើ ជម្រាល (១, ២) គឺស្មើនឹង ជម្រាល (1, ខ្ញុំ) ដោយ ការត្រួតពិនិត្យផលិតផលឆ្លងដូចដែលយើងបានឃើញខាងលើ.

ក្បួនដោះស្រាយ

  1. យើងប្រើមុខងារប៊ូលីន checkStraightLine () ដើម្បីត្រឡប់ថាតើចំនុចមួយដែលបានបញ្ជូនទៅវាបង្កើតជាបន្ទាត់ត្រង់
  2. ប្រសិនបើអារេមានតែ 2 ចំនុច៖
    • ត្រឡប់ពិត។
  3. ចាប់ផ្ដើម x0 ជាកូអរដោនេ x នៃចំណុចទីមួយនិង y0 ជា y-កូអរដោនេនៃចំណុចទីពីរ។ ស្រដៀងគ្នានេះដែរ (x១, ១) សម្រាប់កូអរដោនេនៃចំណុចទីពីរ
  4. ដោយសារយើងត្រូវការភាពខុសគ្នារបស់ពួកគេសម្រាប់ការត្រួតពិនិត្យផលិតផលសូមរក្សាទុកភាពខុសគ្នារបស់ពួកគេដូចជា៖
    • dx = x1 - x0
    • dy = y1 - y0
  5. ឥឡូវសំរាប់ចំនុចទាំងអស់នៅក្នុងអារេបន្ទាប់ពីចំនុចទី ២៖
    1. ទុកកូអរដោនេ x និង y នៃចំនុចនេះក្នុងអថេរ x និង y
    2. ឥឡូវនេះយើងពិនិត្យមើលថាតើជម្រាលនៃចំណុចពីរដំបូងនិងជម្រាលនៃចំណុចនេះនិងចំណុចដំបូងគឺដូចគ្នាដែរឬទេ:
      • If dy * (x - x០) 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

ការវិភាគស្មុគស្មាញនៃការត្រួតពិនិត្យប្រសិនបើវាជាដំណោះស្រាយឡេឡេលេខកូដត្រង់

ស្មុគស្មាញពេលវេលា

O (N) ដែល N = ចំនួនចំនុចនៅក្នុងអារេ។ យើងធ្វើការឆ្លងកាត់តែមួយនៃអារេហើយប្រតិបត្តិការទាំងអស់ដែលបានអនុវត្តនៅក្នុងវាត្រូវការពេលវេលាថេរ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១) ដូចដែលយើងប្រើតែទំហំចងចាំថេរប៉ុណ្ណោះ។