**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.
↵
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
↵
I only know the obvious n! solution. Any solution with better time complexity is appreciated.
