Need help with a geometry Question !!!

Revision en1, by GODOF_Shinobi, 2018-05-30 17:17:19

This question was recently asked in Samsung "Code The Next" contest hosted on hackererth.

Boogle, the software giant developed a mobile operating system named Ambroid. As we all know, in order to unlock an Ambroid device, one needs to draw a pattern connecting the given dots. The developers of Ambroid OS want this pattern unlock to be more secure. So they are wondering, in how many ways, can we draw a pattern by connecting dots.

Given N points (dots) in the co-ordinate system, find and return the number of ways in which, we can draw a pattern by connecting dots.

A pattern is a sequence of distinct dots where two adjacent dots in the sequence are connected by a line segment and should satisfy following conditions.

  • A pattern should connect at least two dots.
  • While connecting two dots A and B, suppose there is a dot C which has not yet been connected and lies on the line segment joining A and B, then you cannot connect A and B without connecting C in between, that is, pattern A-C-B and pattern B-C-A are valid but the patterns A-B or B-A are not valid as C has not yet been connected.

Input 2<=N<=16 0<=x,y<=200.

I only know the obvious n! solution. Any solution with better time complexity is appreciated.

Tags geometry, samsung

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English GODOF_Shinobi 2018-05-30 17:21:09 124
en1 English GODOF_Shinobi 2018-05-30 17:17:19 1282 Initial revision (published)