Number of intersections between pairs of diagonals in a convex polygon

Consider a convex polygon with N vertices, with the additional property that no three diagonals intersect in a single point. Find the number of intersections between pairs of diagonals in such a polygon.

The figure below shows one such polygon with 6 vertices.

-en-img-0001

Note that a polygon is convex if all of its interior angles are less than 180 degrees.

Input

The first and only line of input contains a single integer N,3N100 denoting the number of vertices.

Output

(Number of intersections of diagonals) mod 1000000007

 

For Example :

For N =3 , Output = 0

For N = 4, Output = 1

For N= 6, Output = 15

 

Solution:

A diagonal is a line segment that joins non-adjacent vertices.

So we have to choose any 4 vertices from given vertices.

There are (nC4) ways to choose 4 vertices. If the polygon is strictly convex, then exactly one pair of the lines joining the vertices meets in the interior of the polygon. So the required number of intersection points of diagonals is (nC4).

It is easy to calculate nCr in any programming language.

We recommend to write program by yourself.

C++ implementation to  find Number of intersections between pairs of diagonals in a convex polygon.

#include<iostream>

using namespace std;
const long long int mod = 1000000007;

long long modPow(long long a, long long x, long long p) {
    //calculates a^x mod p in logarithmic time.
    long long res = 1;
    while(x > 0) {
        if( x % 2 != 0) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        x /= 2;
    }
    return res;
}

long long modInverse(long long a, long long p) {
    //calculates the modular multiplicative of a mod m.
    //(assuming p is prime).
    return modPow(a, p-2, p);
}

// Main function to calculate nCr
long long GetNumberOfIntersection(long long n, long long k, long long p) {
// calculates C(n,k) mod p (assuming p is prime).

    long long numerator = 1; // n * (n-1) * ... * (n-k+1)
    for (long long int i=0; i<k; i++) {
        numerator = (numerator * (n-i) ) % p;
    }

    long long denominator = 1; // k!
    for (long long int i=1; i<=k; i++) {
        denominator = (denominator * i) % p;
    }

    // numerator / denominator mod p.
    return ( numerator* modInverse(denominator,p) ) % p;
}

int main()
{
	cin>>n;
	cout<<GetNumberOfIntersection(n,4,mod)<<"\n";
	return 0;
}

Site Footer