CareerCup

package com.code.saurabh.misc;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

import com.code.saurabh.util.UtilClass;

public class PolygonDiagonal {

	public static void main(String[] args) {
		try {
			readInput ("Inputs/polygon.txt");
		} catch (NumberFormatException | IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	private static void readInput(String filename) throws NumberFormatException, IOException {
		File file = new File (filename);
		if (!file.exists()) {
			return;
		}
		
		FileReader fr = new FileReader (filename);
		BufferedReader br = new BufferedReader (fr);
		int totalTest = Integer.parseInt(br.readLine());
		for (int i = 0; i < totalTest; i++) {
			String[] NK = br.readLine().split("\\s+");
			int N = Integer.parseInt(NK[0]);
			int K = Integer.parseInt(NK[1]);
			System.out.println("N: " + N + ", K: " + K + " -> " + calculateDiag (N, K));
		}
	}

	static int calculateDiag (int N, int K) {
		/*It can create a diagonal with all other vertexes than immediate neighbors and its own vertex (count 3) */
		int maxDiagonal = N-3; //Maximum number of diagonals from a vertex
		int totalDiagonal = 0;
		if (maxDiagonal <= 0) {
			return 0;
		}
		
		if (K > maxDiagonal) {
			return 0;
		}
		
		/*This method calculate how many diagonal can be created from a single vertex given constraint*/
		int pointDiagonal = singleVertexDiagonal (K, maxDiagonal);
		
		totalDiagonal = pointDiagonal * N;
		if (K == 1) {
			totalDiagonal = totalDiagonal/2;
		}
		return totalDiagonal;
	}

	private static int singleVertexDiagonal(int k, int maxDiagonal) {
		return factorial (maxDiagonal) / (factorial (maxDiagonal-k) * factorial (k));
	}

	public static int factorial (int N) {
		if (N == 0 || N == 1) {
			return 1;
		}
		return N * factorial (N-1);
	}
}

This is a classic combinatorial problem. Google "PolygonDiagonal".

Can You please tell how did u arrive at the logic for singleVertexDiagonal ?

calculate: (N*(N-3Ck)) / ((N-3)/k)

My idea is to draw a diagonal and divide the polygon

NonIntersectingDiagonals(N, K)
{
  totalSolutions=0;
  if(K==1) return N*(N-3)/2;
  if(N<4) return 0;

  for(int i=3;i<=N-1;i++)
  {
    for(int j=0;j<=K;j++)
    {
      totalSolutions += NonIntersectingDiagonals(i,j)*NonIntersectingDiagonals(N-i+2, K-j);
    }
  }
  return totalSolutions*N;
}