Bài toán
Cho một đa giác lồi n đỉnh, vẽ tất cả các đoạn thẳng nối hai đỉnh bất kì với nhau, đếm xem có bao nhiêu giao điểm nằm thực sự trong đa giác. Giả thiết rằng không có ba đường chéo nào đồng quy.
Độ phức tạp
O(1)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
int n;
main(){
scanf("%d", &n);
printf("%d\n", n/1*(n-1)/2*(n-2)/3*(n-3)/4);
}
Nhận xét
Cứ chọn ra bốn điểm thì tạo ra một giao điểm, vậy nên sẽ có C(4,n) giao điểm.
Cảm ơn bạn Nguyễn Việt Dũng đã giúp tôi hoàn thành bài viết này.