برنامه بررسی هم خطی نقاط – به زبان ساده


در این مطلب، ضمن بیان مفهوم «همخطی» (Collinear)، روش نوشتن برنامه بررسی هم خطی نقاط بیان و پیادهسازی آن در زبانهای برنامهنویسی گوناگون شامل «سیپلاسپلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون» (Python)، «پیاچپی» (PHP) و «سیشارپ» (#C) انجام شده است. «همخطی» (Collinear) مفهومی در هندسه است. بر این اساس، سه نقطه یا بیشتر همخط محسوب میشوند اگر همه روی یک خط راست قرار بگیرند. مجموعه نقاط دارای این خصوصیت را همخط مینامند. در هندسه تحلیلی، در یک فضای nبُعدی، مجموعهای از سه یا تعداد بیشتری نقطه را هم خط گویند اگر و تنها اگر، ماتریس مختصات این بردارها از رتبه ۱ یا کمتر باشد. اکنون، هدف نوشتن برنامه بررسی هم خط بودن نقاط است. برای درک بهتر موضوع، مثال زیر قابل توجه است.
Input : (1, 1), (1, 4), (1, 5) Output : Yes The points lie on a straight line Input : (1, 5), (2, 5), (4, 6) Output : No The points do not lie on a straight line
راهکار اول برای بررسی هم خطی نقاط
سه نقطه روی یک خط راست قرار دارند اگر مساحت مثلث شکل گرفته به وسیله این سه نقطه، صفر باشد.
بنابراین، بررسی میشود که مساحت ناحیه شکل گرفته برابر با صفر است یا نه.
:فرمول محاسبه مساحت مثلث، به صورت زیر است 0.5 * [x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)] :فرمول اساسا نیمی از مقدار دترمینان زیر است x1 x2 x3 y1 y2 y3 1 1 1
پیادهسازی راهکار اول بررسی هم خطی نقاط در ++C
1// C++ program to check if three
2// points are collinear or not
3// using area of triangle.
4#include <bits/stdc++.h>
5#include <math.h>
6#include <stdlib.h>
7
8using namespace std;
9// function to check if point
10// collinear or not
11void collinear(int x1, int y1, int x2,
12 int y2, int x3, int y3)
13{
14 // Calculation the area of
15 // triangle. We have skipped
16 // multiplication with 0.5
17 // to avoid floating point
18 // computations
19 int a = x1 * (y2 - y3) +
20 x2 * (y3 - y1) +
21 x3 * (y1 - y2);
22
23 if (a == 0)
24 cout << "Yes";
25 else
26 cout << "No";
27}
28
29// Driver Code
30int main()
31{
32 int x1 = 1, x2 = 1, x3 = 1,
33 y1 = 1, y2 = 4, y3 = 5;
34 collinear(x1, y1, x2, y2, x3, y3);
35 return 0;
36}
37
38// This code is contributed
39// by Akanksha Rai(Abby_akku)
پیادهسازی راهکار اول بررسی همخطی نقاط در C
1// C program to check if three
2// points are collinear or not
3// using area of triangle.
4#include <stdio.h>
5#include <math.h>
6#include <stdlib.h>
7
8// function to check if point
9// collinear or not
10void collinear(int x1, int y1, int x2,
11 int y2, int x3, int y3)
12{
13 // Calculation the area of
14 // triangle. We have skipped
15 // multiplication with 0.5
16 // to avoid floating point
17 // computations
18 int a = x1 * (y2 - y3) +
19 x2 * (y3 - y1) +
20 x3 * (y1 - y2);
21
22 if (a == 0)
23 printf("Yes");
24 else
25 printf("No");
26}
27
28// Driver Code
29int main()
30{
31 int x1 = 1, x2 = 1, x3 = 1,
32 y1 = 1, y2 = 4, y3 = 5;
33 collinear(x1, y1, x2, y2, x3, y3);
34 return 0;
35}
پیادهسازی راهکار اول بررسی هم خطی نقاط در جاوا
1// Java program to check if
2// three points are collinear
3// or not using area of triangle.
4class GFG
5{
6
7 // function to check if
8 // point collinear or not
9 static void collinear(int x1, int y1, int x2,
10 int y2, int x3, int y3)
11 {
12
13 /* Calculation the area of
14 triangle. We have skipped
15 multiplication with 0.5
16 to avoid floating point
17 computations */
18 int a = x1 * (y2 - y3) +
19 x2 * (y3 - y1) +
20 x3 * (y1 - y2);
21
22 if (a == 0)
23 System.out.println("Yes");
24 else
25 System.out.println("No");
26 }
27
28 // Driver Code
29 public static void main(String args[])
30 {
31 int x1 = 1, x2 = 1, x3 = 1,
32 y1 = 1, y2 = 4, y3 = 5;
33
34 collinear(x1, y1, x2, y2, x3, y3);
35
36 }
37}
38
39// This code is contributed by Sam007.
پیادهسازی راهکار اول بررسی هم خطی نقاط در پایتون
1# Python program to check
2# if three points are collinear
3# or not using area of triangle.
4
5# function to check if
6# point collinear or not
7def collinear(x1, y1, x2, y2, x3, y3):
8
9 """ Calculation the area of
10 triangle. We have skipped
11 multiplication with 0.5 to
12 avoid floating point computations """
13 a = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)
14
15 if (a == 0):
16 print "Yes"
17 else:
18 print "No"
19
20# Driver Code
21x1, x2, x3, y1, y2, y3 = 1, 1, 1, 1, 4, 5
22collinear(x1, y1, x2, y2, x3, y3)
23
24# This code is contributed
25# by Sachin Bisht
پیادهسازی راهکار اول بررسی هم خطی نقاط در سیشارپ
1// C# program to check if
2// three points are collinear
3// or not using area of triangle.
4using System;
5
6class GFG
7{
8
9 /* function to check if
10 point collinear or not */
11 static void collinear(int x1, int y1, int x2,
12 int y2, int x3, int y3)
13 {
14
15 /* Calculation the area of
16 triangle. We have skipped
17 multiplication with 0.5 to
18 avoid floating point computations */
19 int a = x1 * (y2 - y3) +
20 x2 * (y3 - y1) +
21 x3 * (y1 - y2);
22
23 if (a == 0)
24 Console.Write("Yes");
25 else
26 Console.Write("No");
27 }
28
29 // Driver code
30 public static void Main ()
31 {
32 int x1 = 1, x2 = 1, x3 = 1,
33 y1 = 1, y2 = 4, y3 = 5;
34
35 collinear(x1, y1, x2, y2, x3, y3);
36 }
37}
38
39// This code is contributed by Sam007.
پیادهسازی راهکار اول بررسی هم خطی نقاط در PHP
1<?php
2// PHP or not using area of triangle.
3
4/* function to check if
5point collinear or not */
6function collinear($x1, $y1, $x2,
7 $y2, $x3, $y3)
8{
9 /* Calculation the area of
10 triangle. We have skipped
11 multiplication with 0.5 to
12 avoid floating point computations */
13 $a = $x1 * ($y2 - $y3) +
14 $x2 * ($y3 - $y1) +
15 $x3 * ($y1 - $y2);
16
17 if ($a == 0)
18 printf("Yes");
19 else
20 printf("No");
21}
22
23// Driver Code
24$x1 = 1; $x2 = 1; $x3 = 1;
25$y1 = 1; $y2 = 4; $y3 = 5;
26collinear($x1, $y1, $x2, $y2, $x3, $y3);
27
28// This code is contributed by Sam007.
29?>
خروجی قطعه کدهای بالا (برای نقاطی که به برنامه داده شده است)، به صورت زیر است.
Yes
راهکار دوم برای بررسی هم خطی نقاط
برای سه نقطه، شیب هر جفت از نقاط باید با شیب دیگر جفت نقاط، برابر باشد.
برای مثال، شیب خطی که (x2, y2) و (x3, y3) را به یکدیگر متصل میکند، باید مشابه باشد.
(y3 - y2)/(x3 - x2) = (y2 - y1)/(x2 - x1)
به عبارت دیگر:
(y3 - y2)(x2 - x1) = (y2 - y1)(x3 - x2)
اگر خروجی این رابطه، برابر با صفر باشد، یعنی نقاط روی یک خط راست قرار دارند و در واقع، همخط هستند.
پیادهسازی راهکار دوم بررسی هم خطی نقاط در C
1// Slope based solution to check
2// if three points are collinear.
3#include <stdio.h>
4#include <math.h>
5
6/* function to check if
7point collinear or not*/
8void collinear(int x1, int y1, int x2,
9 int y2, int x3, int y3)
10{
11 if ((y3 - y2) * (x2 - x1) ==
12 (y2 - y1) * (x3 - x2))
13 printf("Yes");
14 else
15 printf("No");
16}
17
18// Driver Code
19int main()
20{
21 int x1 = 1, x2 = 1, x3 = 0,
22 y1 = 1, y2 = 6, y3 = 9;
23 collinear(x1, y1, x2, y2, x3, y3);
24 return 0;
25}
پیادهسازی راهکار دوم بررسی هم خطی نقاط در جاوا
1// Slope based solution to check
2// if three points are collinear.
3
4import java.io.*;
5
6class GFG {
7
8/* function to check if
9point collinear or not*/
10static void cool_line(int x1, int y1, int x2,
11 int y2, int x3, int y3)
12{
13 if ((y3 - y2) * (x2 - x1) ==
14 (y2 - y1) * (x3 - x2))
15 System.out.println("Yes");
16 else
17 System.out.println("No");
18}
19
20// Driver Code
21
22 public static void main (String[] args) {
23 int a1 = 1, a2 = 1, a3 = 0,
24 b1 = 1, b2 = 6, b3 = 9;
25 cool_line(a1, b1, a2, b2, a3, b3);
26
27
28 }
29}
30//This Code is Contributed by ajit
پیادهسازی راهکار دوم بررسی هم خطی نقاط در پایتون
1# Slope based solution to check if three
2# points are collinear.
3
4# function to check if
5# point collinear or not
6def collinear(x1, y1, x2, y2, x3, y3):
7
8 if ((y3 - y2)*(x2 - x1) == (y2 - y1)*(x3 - x2)):
9 print ("Yes")
10 else:
11 print ("No")
12
13# Driver Code
14x1, x2, x3, y1, y2, y3 = 1, 1, 0, 1, 6, 9
15collinear(x1, y1, x2, y2, x3, y3);
16
17# This code is contributed
18# by Sachin Bisht
پیادهسازی راهکار دوم بررسی هم خطی نقاط در سیشارپ
1// Slope based solution to check
2// if three points are collinear.
3using System;
4
5class GFG
6{
7
8/* function to check if
9point collinear or not*/
10static void cool_line(int x1, int y1, int x2,
11 int y2, int x3, int y3)
12{
13 if ((y3 - y2) * (x2 - x1) ==
14 (y2 - y1) * (x3 - x2))
15 Console.WriteLine("Yes");
16 else
17 Console.WriteLine("No");
18}
19
20// Driver Code
21static public void Main ()
22{
23 int a1 = 1, a2 = 1, a3 = 0,
24 b1 = 1, b2 = 6, b3 = 9;
25 cool_line(a1, b1, a2, b2, a3, b3);
26}
27}
28
29// This code is contributed by ajit
پیادهسازی راهکار دوم بررسی هم خطی نقاط در PHP
1<?php
2// Slope based solution to check
3// if three points are collinear.
4
5/* function to check if
6point collinear or not*/
7function collinear($x1, $y1, $x2,
8 $y2, $x3, $y3)
9{
10 if (($y3 - $y2) * ($x2 - $x1) ==
11 ($y2 - $y1) * ($x3 - $x2))
12 echo ("Yes");
13 else
14 echo ("No");
15}
16
17// Driver Code
18$x1 = 1;
19$x2 = 1;
20$x3 = 0;
21$y1 = 1;
22$y2 = 6;
23$y3 = 9;
24collinear($x1, $y1, $x2,
25 $y2, $x3, $y3);
26
27// This code is contributed by ajit
28?>
خروجی قطعه کد بالا به صورت زیر است.
No
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش برنامهنویسی C++
- مجموعه آموزشهای ریاضیات
- یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
- الگوریتم بازی مار و پله همراه با کد — به زبان ساده
- حل مساله n وزیر با الگوریتم پسگرد (Backtracking) — به زبان ساده
- الگوریتم جست و جوی دودویی در جاوا اسکریپت — به زبان ساده
^^