การนับสามเหลี่ยมที่มีทั้งหมด n จุดโดยมี m collinear ใน C++

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

จุดคอลลิเนียร์ − จุดที่อยู่บนเส้นเดียวกันเรียกว่า collinear คะแนน 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 collinear คือ − 9

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

ป้อนข้อมูล − n=10, m=5

ผลผลิต − จำนวนสามเหลี่ยมที่มีทั้งหมด n จุดที่มี m collinear คือ − 110

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

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

เราจะสร้างสามเหลี่ยมปาสกาลสำหรับการคำนวณชุดค่าผสม ทุกแถวคำนวณโดยใช้การเพิ่มคอลัมน์แถวก่อนหน้า

• ใช้ตัวแปร n และ m เป็นอินพุตสำหรับจุดจำนวนหนึ่ง

• ฟังก์ชัน collinear_points(int n,int m) รับ n และ m แล้วคืนค่าจำนวนสามเหลี่ยมที่มีทั้งหมด n จุดโดยมี m collinear

• Set count =ตรวจสอบ (n, 3) - ตรวจสอบ (m, 3); ( สำหรับคำนวณ nC₃ - mC₃ )

• ตรวจสอบฟังก์ชัน (int n, int r) รับ n และ r และส่งคืนค่า nC_r

• ใช้อาร์เรย์ arr ที่มีความยาว r+1

• ตั้งค่าทั้งอาร์เรย์ด้วย 0 โดยใช้ memset

• ตั้งค่า arr[0] =1.

• ใช้ two for loops จาก i=0 ถึง i<=n. และ j=min (i,r) ถึง j>0 คำนวณสามเหลี่ยมปาสกาลเป็น arr[j]=arr[j]+arr[j-1]

• ในที่สุดเราจะได้ arr[r] เป็น nC_r . คืนสินค้า

• หลังจากสิ้นสุดฟังก์ชัน check() จะได้นับสามเหลี่ยม

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

#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