จำนวนสามเหลี่ยมจาก n จุดทั้งหมดที่มี m จุดอยู่บนเส้นตรงเดียวกันใน C++

เราได้รับตัวแปรสองตัว n และ m แทนจำนวนจุดบนระนาบ 2 มิติ จาก n จุด m จุดอยู่บนเส้นตรงเดียวกัน (collinear) เป้าหมายคือหาจำนวนสามเหลี่ยมที่สามารถสร้างได้โดยใช้นจุดเหล่านี้

จุด一直線 (Collinear points) - จุดที่อยู่บนเส้นตรงเดียวกันเรียกว่าจุด一直線 จุด A และ B เป็นจุด一直線

กำหนด n=4 (A,B,C,D), m=2 (A,B)

จำนวนสามเหลี่ยม -

เลือกจุดใดๆ สามจุดจาก 4 = 4C₃

แตจุด一直線ไม่สามารถสร้างสามเหลี่ยมได้ ดังนั้นลบสามเหลี่ยมที่เป็นไปได้ที่จะนับข้างต้น = 2C₃

สามเหลี่ยมทั้งหมด = 4C₃ - 2C₃ = 4 - 0 = 4 (ABC, ACD, BCD, ABD)

สำหรับ n และ m = nC₃ - mC₃

ตัวอย่าง

อินพุต - n=5, m=3

เอาต์พุต - จำนวนสามเหลี่ยมจาก n จุดทั้งหมดที่มี m จุดอยู่บนเส้นตรงเดียวกันคือ - 9

คำอธิบาย - สามเหลี่ยมทั้งหมด = 5C₃ - 3C₃ = 10 - 1 = 9

อินพุต - n=10, m=5

เอาต์พุต - จำนวนสามเหลี่ยมจาก n จุดทั้งหมดที่มี m จุดอยู่บนเส้นตรงเดียวกันคือ - 110

คำอธิบาย - สามเหลี่ยมทั้งหมด = 10C₃ - 5C₃ = 120 - 10 = 110

แนวทางที่ใช้ในโปรแกรมด้านล่าง

เราจะสร้างสามเหลี่ยมปาสคาล (Pascal's Triangle) สำหรับการคำนวณการจัดหมู่ (combinations) ทุกแถวคำนวณโดยการบวกคอลัมน์ของแถวก่อนหน้า

รับตัวแปร n และ m เป็นอินพุตสำหรับจำนวนจุด
ฟังก์ชัน collinear_points(int n, int m) รับ n และ m คืนค่าจำนวนสามเหลี่ยมจาก n จุดทั้งหมดที่มี m จุดอยู่บนเส้นตรงเดียวกัน
ตั้ง count = check(n, 3) - check(m, 3) (สำหรับการคำนวณ nC₃ - mC₃)
ฟังก์ชัน check(int n, int r) รับ n และ r คืนค่าของ nC_r
สร้างอาร์เรย์ arr ความยาว r+1
ตั้งอาร์เรย์ทั้งหมดเป็น 0 ด้วย memset
ตั้ง arr[0] = 1
ใช้ลูป for สองอันจาก i=0 ถึง i<=n และ j=min(i,r) ถึง j>0 คำนวณสามเหลี่ยมปาสคาลเป็น arr[j]=arr[j]+arr[j-1]
ที่สุดเราจะได้ arr[r] เป็น nC_r คืนค่ามัน
หลังจบฟังก์ชัน check() เราจะได้จำนวนสามเหลี่ยม
คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

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

int check(int n, int r){ 
    int arr[r+1]; 
    memset(arr, 0, sizeof(arr)); 
    arr[0] = 1; 
    for (int i = 1; i <= n; i++){ 
        for (int j = min(i, r); j > 0; j--){ 
            arr[j] = arr[j] + arr[j-1]; 
        } 
    } 
    return arr[r]; 
} 

int collinear_points(int n,int m){ 
    int count = check(n, 3) - check(m, 3); 
    return count; 
} 

int main(){ 
    int n = 6, m = 2; 
    cout << "Count of triangles with total n points with m collinear are: " << collinear_points(n, m); 
    return 0; 
}

เอาต์พุต

Count of triangles with total n points with m collinear are: 20