Table of Contents
Points in a Plane – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Points in a Plane HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */#include<iostream>
#include<set>
#include<map>
#include<string>
#include<stdio.h>
#include<sstream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<string.h>
using namespace std ;
#define MOD 1000000007
#define INF (int)1e9
#define MAXN 20
typedef pair<int,int> P ;
int n,pre[MAXN],fac[MAXN],x[MAXN],y[MAXN] ;
int col[MAXN][MAXN] ;
char bit[1 << MAXN] ;
char good[1 << MAXN] ;
char best[1 << MAXN] ;
char valid[1 << MAXN] ;
char vid,id[1 << MAXN] ;
int memo[1 << MAXN] ;
int solve(int mask)
{
if(bit[mask] <= 2) return 1 ;
if(id[mask] == vid) return memo[mask] ;
if(good[mask]) return pre[bit[mask]] ;
id[mask] = vid ;
int j,nmask = mask ;
for(j = 0;j < n;j++) if(mask & 1 << j)
{
nmask ^= 1 << j ;
break ;
}
int ways = 0,can = best[mask] ;
if(best[nmask] == can - 1) ways = solve(nmask) ;
for(int i = nmask;i > 0;i = ((i - 1) & nmask))
{
int k = i | 1 << j ;
if(valid[k] && best[mask ^ k] == can - 1)
{
ways += solve(mask ^ k) ;
if(ways >= MOD) ways -= MOD ;
}
}
return memo[mask] = ways ;
}
void generate()
{
for(int tt = 0;tt < 10;tt++)
{
char in[] = "in .txt" ;
in[2] = tt + '0' ;
FILE * fout = fopen(in,"w") ;
int runs = 50 ;
fprintf(fout,"%d\n",runs) ;
for(int j = 0;j < runs;j++)
{
n = rand() % 18 ;
if(tt == 8) n = 18 ;
char vis[102][102] ;
memset(vis,0,sizeof vis) ;
for(int i = 0;i < n;i++)
{
if(tt < 3 && j < 15)
{
x[i] = rand() % 10 ;
y[i] = rand() % 10 ;
}
else if(tt < 6 && j < 15)
{
x[i] = rand() % 5 ;
y[i] = rand() % 5 ;
}
else if(tt < 10 && j < 15)
{
x[i] = i ;
y[i] = i + (rand() % 5 - 2) ;
if(y[i] < 0) y[i] = i ;
}
else
{
x[i] = rand() % 100 + 1 ;
y[i] = rand() % 100 + 1 ;
}
if(vis[x[i]][y[i]]) { i-- ; continue ; }
vis[x[i]][y[i]] = 1 ;
}
fprintf(fout,"%d\n",n) ;
for(int i = 0;i < n;i++) fprintf(fout,"%d %d\n",x[i],y[i]) ;
}
fclose(fout) ;
}
}
int main()
{
fac[0] = 1 ;
for(int i = 1;i < MAXN;i++) fac[i] = 1LL * i * fac[i - 1] % MOD ;
for(int i = 1;i < 1 << MAXN;i++) bit[i] = bit[i >> 1] + (i & 1) ;
pre[0] = pre[1] = 1 ;
for(int i = 2;i < MAXN;i++)
{
pre[i] = 1LL * pre[i - 2] * (i - 1) % MOD ;
if(i % 2 == 1) pre[i] += pre[i - 1] ;
pre[i] %= MOD ;
}
// generate() ; return 0 ;
int runs ;
scanf("%d",&runs) ;
while(runs--)
{
scanf("%d",&n) ;
for(int i = 0;i < n;i++) scanf("%d%d",&x[i],&y[i]) ;
memset(col,0,sizeof col) ;
for(int k1 = 0;k1 < n;k1++)
for(int k2 = 0;k2 < n;k2++)
{
for(int j = 0;j < n;j++)
{
int area = x[j] * (y[k1] - y[k2]) + x[k1] * (y[k2] - y[j]) + x[k2] * (y[j] - y[k1]) ;
if(area == 0) col[k1][k2] |= 1 << j ;
}
}
for(int i = 0;i < 1 << n;i++)
{
if(bit[i] <= 2) { valid[i] = true ; continue ; }
for(int j = 0;j < n;j++) if(i & 1 << j)
{
int k1 = -1 ;
for(int k = j + 1;k < n;k++) if(i & 1 << k) { k1 = k ; break ; }
if((col[j][k1] | i) == col[j][k1]) valid[i] = true ;
else valid[i] = false ;
break ;
}
}
best[0] = 0 ;
for(int i = 1;i < 1 << n;i++)
{
if(bit[i] == 1) { best[i] = 1 ; continue ; }
int j;
for(j = 0;j < n;j++) if(i & 1 << j) break ;
int cret = n ;
for(int k = j + 1;k < n;k++)
if(i & 1 << k)
cret = min(cret,1 + best[i & ~col[j][k]]) ;
best[i] = cret ;
}
for(int i = 0;i < 1 << n;i++)
{
good[i] = 1 ;
if(bit[i] <= 2) continue ;
int j;
for(j = 0;j < n;j++) if(i & 1 << j) break ;
if(!good[i ^ 1 << j]) { good[i] = 0 ; continue ; }
for(int k = j + 1;k < n;k++)
if(i & 1 << k)
if(bit[i & col[j][k]] > 2)
good[i] = 0 ;
}
int tot = best[(1 << n) - 1] ;
vid++ ;
int ret = solve((1 << n) - 1) ;
ret = 1LL * ret * fac[tot] % MOD ;
printf("%d %d\n",tot,ret) ;
}
return 0 ;
}
Java Points in a Plane HackerRank Solution
import java.util.*;
import java.io.*;
class Solution
{
BufferedReader input;
BufferedWriter out;
StringTokenizer token;
int N;
int[] x,y;
int[] dp,dp3;
boolean[] ok;
int[] member;
int mod = 1000000007;
int BitCount(int x)
{
int ret = 0;
while(x > 0)
{
if( (x&1) != 0 ) ret++;
x >>= 1;
}
return ret;
}
boolean collinear(int set)
{
int ctr = 0;
for(int i = 0; set > 0; i++)
{
if( (set&1) != 0 )
member[ctr++] = i;
set >>= 1;
}
if(ctr <= 2)return true;
int a = x[member[0]]-x[member[1]];
int b = y[member[0]]-y[member[1]];
for(int i = 2; i < ctr; i++)
{
int aa = x[member[0]]-x[member[i]];
int bb = y[member[0]]-y[member[i]];
if(aa*b != a*bb)return false;
}
return true;
}
String binary(int x)
{
String ret = "";
for(int i = 0; i < N; i++)
{
if( ((x>>i)&1) == 0) ret = "0"+ret;
else ret = "1"+ret;
}
return ret;
}
void solve() throws IOException
{
long qq = System.currentTimeMillis();
input = new BufferedReader(new InputStreamReader(System.in));
out = new BufferedWriter(new OutputStreamWriter(System.out));
int T = nextInt();
int twoMax = (1<<16);
dp = new int[twoMax];
x = new int[16];
y = new int[16];
ok = new boolean[twoMax];
dp3 = new int[twoMax];
member = new int[16];
ArrayList<Integer> o;
for(int t = 0; t < T; t++)
{
N = nextInt();
int twoN = (1<<N);
for(int i = 0; i < N; i++)
{
x[i] = nextInt();
y[i] = nextInt();
}
o = new ArrayList<Integer>();
for(int i = twoN-1; i > 0; i--)
{
ok[i] = false;
if(collinear(i))
{
ok[i] = true;
o.add(i);
}
}
Arrays.fill(dp,-1);
dp[0] = 0;
dp3[0] = 1;
int m = 0;
for(int i = 0; i < o.size(); i++)
{
int ii = o.get(i);
for(int j = m; j >= 0; j--)
{
if((ii&j) == 0 && dp[j] != -1)
{
m = Math.max(m,j|ii);
if(dp[j|ii] == -1 || dp[j|ii] > 1+dp[j])
{
dp[j|ii] = 1+dp[j];
dp3[j|ii] = (int)(((long)(dp[j]+1)*dp3[j])%mod);
}
else if(dp[j|ii] == 1+dp[j])
{
dp3[j|ii] += ((long)(dp[j]+1)*dp3[j])%mod;
dp3[j|ii] %= mod;
}
}
}
}
out.write(""+ dp[(twoN)-1] + " " + dp3[(twoN)-1]);
out.newLine();
}
out.flush();
out.close();
input.close();
}
int nextInt() throws IOException
{
if(token == null || !token.hasMoreTokens())
token = new StringTokenizer(input.readLine());
return Integer.parseInt(token.nextToken());
}
Long nextLong() throws IOException
{
if(token == null || !token.hasMoreTokens())
token = new StringTokenizer(input.readLine());
return Long.parseLong(token.nextToken());
}
String next() throws IOException
{
if(token == null || !token.hasMoreTokens())
token = new StringTokenizer(input.readLine());
return token.nextToken();
}
public static void main(String[] args) throws Exception
{
new Solution().solve();
}
}
Python 3 Points in a Plane HackerRank Solution
Suggest in comments
Python 2 Points in a Plane HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
def constdr1(Points) :
Droites = []
i = 0
j = i + 1
while j < len(Points) :
S = True
for D in Droites :
if (Points[D[1]][0]-Points[D[0]][0])*(Points[j][1]-Points[i][1])-(Points[D[1]][1]-Points[D[0]][1])*(Points[j][0]-Points[i][0])== 0 :
S=False
if not (j in D) :
D.append(j)
break
if S :
Droites.append([i,j])
j+=1
return Droites
def sousparties(D) :
N = len(D)
D2 = D +[]
if N==0 :
return [[]]
else :
i =D2[0]
D2.pop(0)
Sol = sousparties(D2)
Sol2 = []
for P in Sol :
Sol2.append([i]+P)
return Sol2 + Sol
def factorielle(n) :
if n == 0 :
return 1
else :
return n*factorielle(n-1)
def main(Points, d,nbp) :
if len(Points)< 3 :
nb= nbp + len(Points)
k = (nb+1)/2
if k > d :
return [d,0]
else :
return [k,factorielle(2*k)/2**k]
elif d == 0 :
#print "plop2"
return [0,0]
else :
Droites = constdr1(Points)
i = 0
sol = 0
while i< len(Droites) :
Droites[i].pop(0)
for P in sousparties(Droites[i]) :
if len(P) < 2 :
continue
j=1
Points2 = []
while j < len(Points) :
if not j in P :
Points2.append(Points[j])
j+=1
A = main(Points2,d-1,nbp)
if A[0]<d-1:
d = A[0] +1
sol = d*A[1]
else :
sol +=d*A[1]
i+=1
A = main(Points[1:],d, nbp+1)
if A[0]<d:
d = A[0]
sol = A[1]
else:
sol +=A[1]
#print sol
return [d,int(sol %1000000007)]
T = map(eval, raw_input().split())
i = 0
while i < T[0] :
M = map(eval, raw_input().split())
N= M[0]
j = 0
points = []
while j < N:
X, Y = map(eval, raw_input().split())
points += [[X,Y]]
j+=1
Sol = main(points, (N+1)/2,0)
print Sol[0], Sol[1]
i+=1
C Points in a Plane HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#define P 1000000007
long long g=1,p[20][2],t,tt,v,kon,a[20][70000][2],b[70000],i,j,k,l,m,n,maz[70000],mmaz[70000];
void uloz(long long mam, long long ind, long long vv)
{
if(ind ==n) {mmaz[mam]=1;return;}
uloz(mam, ind+1,vv);
if(vv&(1<<ind)) uloz(mam+(1<<ind),ind+1,vv);
return;
}
void priamka(long long xx, long long yy)
{
long long vv=0,ii;
for(ii=0;ii<n;ii++)
{
vv*=2;
if((p[ii][0]-p[xx][0])*(p[yy][1]-p[xx][1]) == (p[ii][1]-p[xx][1])*(p[yy][0]-p[xx][0]))
vv++;
}
if(maz[vv]==0) uloz(0,0,vv);
maz[vv]=1;
return;
}
/*
void makaj1(long long ind, long long ii, long long vv, long long mam, long long dl)
{
if(dl==n)
{
if(mam==0) return;
if(mam > vv) {printf("chuj\n"); return;}
if(b[mam]!=g)
{
// printf("..%lld: %lld %lld %lld=vv\n",ind,ii,mam,vv);
b[mam]=g;
a[ind][ii^mam][1] = 1;
a[ind][ii^mam][0] = (a[ind][ii^mam][0] + a[ind-1][ii][0])%P;
}
return;
}
makaj1(ind,ii,vv,mam,dl+1);
if(vv&(1<<dl)) makaj1(ind,ii,vv,mam+(1<<dl),dl+1);
return;
}
*/
void pocitaj(long long ind)
{
long long ii,jj,kk,min;
for(ii=0;ii<(1<<n);ii++) {a[ind][ii][0]=0;a[ind][ii][1]=0;}
for(ii=0;ii<(1<<n);ii++)
if(a[ind-1][ii][1] && mmaz[ii])
{
a[ind][0][1] = 1;
a[ind][0][0] = (a[ind][0][0] + a[ind-1][ii][0])%P;
kon=1;
}
//printf("%lld=kon\n",kon);
if(kon) return;
a[ind][0][0]=0;
a[ind][0][1]=0;
for(ii=0;ii<(1<<n);ii++)
if(a[ind-1][ii][1])
{
g++;
while(((1<<min)&ii) == 0) min++;
for(jj=0;jj<l;jj++)
// if(kk=(maz[jj]&ii)) makaj1(ind,ii,kk,0,0);
if(b[kk=(ii&maz[jj])]!=g && (kk&(1<<min)))
{
b[kk]=g;
a[ind][ii^kk][1] = 1;
a[ind][ii^kk][0] = (a[ind][ii^kk][0] + a[ind-1][ii][0])%P;
}
}
//kon=1;
return;
}
int main()
{
scanf("%lld",&t);
for(tt=0;tt<t;tt++)
{
scanf("%lld",&n);
for(i=0;i<n;i++) scanf("%lld %lld",&p[i][0],&p[i][1]);
for(i=0;i<(1<<n);i++) {maz[i]=0;mmaz[i]=0;}
// for(i=0;i<n;i++) {mmaz[(1<<i)]=1;maz[(1<<i)]=1;}
if(n==1) {mmaz[1]=1;maz[1]=1;}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
priamka(i,j);
// printf("%lld %lld -> %lld\n",i,j,priamka(i,j));
}
for(i=0;i<(1<<n);i++) maz[i]=mmaz[i];
l=0;
for(i=1;i<(1<<n);i++)
if(maz[i]) maz[l++] = i;
//printf("%lld\n",l);
//for(i=0;i<l;i++) printf("%lld..\n",maz[i]);
k=0;
for(i=0;i<(1<<n);i++) a[0][i][1]=0;
a[0][(1<<n)-1][1] = 1;
a[0][(1<<n)-1][0] = 1;
kon=0;
i=0;
while(kon==0)
{
i++;
pocitaj(i);
// for(j=0;j<(1<<n);j++) printf("%lld %lld---> %lld\n",i,j,a[i][j][0]);
}
v = a[i][0][0];
for(j=2;j<=i;j++) v= (v*j)%P;
printf("%lld %lld\n",i,v);
}
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
