වලංගු බූමරන්ග් ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ගූගල්
ගණිතය

ගැටළු ප්රකාශය

මෙම ගැටළුවේදී, අපට XY 2-D තලයක ලකුණු තුනක් ලබා දී ඇත. ඔවුන් බූමරැන්ග් එකක් සෑදුවත් නැතත්, එනම් ඔවුන් තිදෙනා වේවා යන්න අප ආපසු යා යුතුය සුවිශේෂී වේ ලකුණු සහ කරන්න නැත සරල රේඛාවක් සාදන්න.

උදාහරණයක්

Points = {{1 , 2} , {2 , 6} , {1 , 2}}
false
Points = {{1 , 1} , {2 , 3} , {6 , 7}}
true

පළමු ආදානයට 3 න් සමාන ලකුණු දෙකක් ඇත, එබැවින් එය වලංගු බූමරන්ග් එකක් නොවන අතර අපි ව්‍යාජ ලෙස මුද්‍රණය කරමු. දෙවන පරීක්ෂණයට සරල ලක්ෂ්‍ය 3 ක් ඇති අතර එය සරල රේඛාවක් සාදන්නේ නැත.

වලංගු බූමරන්ග් ලීට්කෝඩ් විසඳුම

ප්‍රවේශය (බෑවුම් පරීක්ෂණය)

ගැටලුවේ එය සෘජු රේඛාවක් දැයි පරීක්ෂා කරන්න, සෑම ලක්ෂ්‍ය යුගලයක් විසින්ම සාදන ලද රේඛාවේ බෑවුම සමාන නම් එකිනෙකට වෙනස් ලක්ෂ්‍ය තුනක් පමණක් රේඛීය බව අපි ඉගෙන ගෙන ඇත්තෙමු. මෙන්න, අපි පරීක්ෂා කළ යුතුය:

  • ලකුණු වෙනස් නම්
  • ලකුණු සරල රේඛාවක් මත නොපවතී

කිසියම් ලක්ෂ්‍ය යුගලයක් සමාන නම්, ලබා දී ඇති ආදානය ඕනෑම ලක්ෂ්‍ය 2 ක් (හෝ තනි ලක්ෂ්‍යයක්) සැමවිටම කොලීනියර් වන බැවින් සහසම්බන්ධතා පරීක්ෂණය සමත් වේ. ඉතින්, අපි බෑවුම්වල සමානාත්මතාවය පරීක්ෂා කළ යුතුයි. P1, P2 සහ P3 යන ලක්ෂ්‍ය තුන කොලීනියර් නම්, අපට ඇති බව සලකන්න

(y2 - y1): (x2 - x1) :: (y3 - y2): (x3 - x2), හෝ

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

මෙහි x1, x2, x3, y1, y2, y3 යනු P1, P2 සහ P3 හි අනුරූප x සහ t ඛණ්ඩාංක වේ.

ඇල්ගොරිතම

  1. ආරම්භ කරන්න dx1 = හි වෙනස x- ඛණ්ඩාංක පළමු කරුණු දෙකෙන් සහ dy1 = හි වෙනස y- ඛණ්ඩාංක පළමු ලකුණු දෙකෙන්
  2. ඒ හා සමානව, ගබඩා dx2 = වෙනස y- ඛණ්ඩාංක අවසාන ලකුණු දෙකෙන් සහ dy2 = හි වෙනස y- ඛණ්ඩාංක අවසාන ලකුණු දෙකෙන්
  3. ((Dx1 * dy2)! = (Dx2 * dy1)) නම් ආපසු යන්න (බෑවුම් පරීක්ෂණය තත්වය)
  4. ප්‍රති .ලය මුද්‍රණය කරන්න

වලංගු බූමරන්ග් ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#include <bits/stdc++.h>
using namespace std;

bool isBoomerang(vector <vector <int> > &points)
{
    int dx1 = (points[1][0] - points[0][0]);
    int dy1 = (points[1][1] - points[0][1]);
    int dx2 = (points[2][0] - points[1][0]);
    int dy2 = (points[2][1] - points[1][1]);

    return (dx1 * dy2) != (dy1 * dx2);
}

int main()
{
    vector <vector <int> > points = {{1 , 1} , {2 , 3} , {6 , 7}};
    if(isBoomerang(points))
        cout << "true\n";
    else
        cout << "false\n";
    return 0;
}

ජාවා වැඩසටහන

class valid_boomerang
{
    public static void main(String args[])
    {
        int[][] points = {{1 , 1} , {2 , 3} , {6 , 7}};
        if(isBoomerang(points))
            System.out.println("true");
        else
            System.out.println("false");
    }

    static boolean isBoomerang(int[][] points)
    {
        int dx1 = (points[1][0] - points[0][0]);
        int dy1 = (points[1][1] - points[0][1]);
        int dx2 = (points[2][0] - points[1][0]);
        int dy2 = (points[2][1] - points[1][1]);

        return (dx1 * dy2) != (dy1 * dx2);
    }
}
true

වලංගු බූමරන්ග් ලීට්කෝඩ් විසඳුමේ සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (1) අපි නියත මෙහෙයුම් ගණනක් කරන විට.

අවකාශයේ සංකීර්ණතාව

ඕ (1) අපි නිරන්තර මතක අවකාශය භාවිතා කරන නිසා.