HackerRank Points in a Plane Problem Solution

In this post, we will solve HackerRank Points in a Plane Problem Solution.

There are N points on an XY plane. In one turn, you can select a set of collinear points on the plane and remove them. Your goal is to remove all the points in the least number of turns. Given the coordinates of the points, calculate two things:

The minimum number of turns (T) needed to remove all the points.
The number of ways to to remove them in T turns. Two ways are considered different if any point is removed in a different turn.

Input Format

The first line contains the number of test cases T. T test cases follow. Each test case contains N on the first line, followed by N lines giving the coordinates of the points.

Constraints

1 <= T <= 50
1 <= N <= 16
0 <= xi,yi <= 100
No two points will have the same coordinates.

Output Format

Output T lines, one for each test case, containing the least number of turns needed to remove all points and the number of ways to do so. As the answers can be large, output them modulo 1000000007.

Sample Input

Sample Output

2 6  
2 8

Explanation

For the 1st input, Let the points be labelled p1,p2,p3. These are the ways to remove them (first turn’s points, followed by second turn’s points):

a. 1) p1,p2 2) p3
b. 1) p1,p3 2) p2
c. 1) p2,p3 2) p1
d. 1) p3 2) p1,p2
e. 1) p2 2) p1,p3
f. 1) p1 2) p3,p2

Table of Contents

Points in a Plane C Solution

#include <stdio.h>

#define P 1000000007

long long g=1,p[20][2],t,tt,v,kon,a[20][70000][2],b[70000];
long long 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 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;
}

Points in a Plane C++ Solution

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,b) for(int i=0;i<(b);i++)

using namespace std;

#define MOD 1000000007
#define MAXN 17
int N, X[MAXN], Y[MAXN], a[MAXN][MAXN];
bool colinear[1 << MAXN];
int dp1[1 << MAXN], dp2[1 << MAXN];

int gcd(int a, int b){ return b ? gcd(b, a%b) : a; }


int CMP;
bool cmp(int x, int y){ return a[CMP][x] < a[CMP][y]; }

int get(int mask){
  if(dp2[mask] != -1) return dp2[mask];
  dp2[mask] = 0;
  int points[MAXN], P = 0;
  REP(j, N) if(mask & (1 << j)) points[P++] = j;
  if(P < 3) return dp2[mask] = 1;
  int mask1 = mask ^ (1 << points[0]);
  if(dp1[mask] - 1 == dp1[mask1]) dp2[mask] = (dp2[mask] + get(mask1)) % MOD;
  int first = points[0];
  CMP = first;
  sort(points + 1, points + P, cmp);
  int start = 0, end = 1;
  while(end < P){
    start = end++;
    while(end < P && a[first][points[start]] == a[first][points[end]]) end++;
    //printf("mask: %d P: %d start: %d end: %d\n", mask, P, start, end);
    FOR(i, 1, (1 << (end - start)) - 1){
      int mask2 = mask1;
      REP(j, end - start) if(i & (1 << j)) mask2 ^= 1 << points[start + j];
      if(dp1[mask] - 1 == dp1[mask2]) dp2[mask] = (dp2[mask] + get(mask2)) % MOD;
    }
  }
  return dp2[mask];
}

int fac(int n){
  int ans = 1;
  REP(i, n) ans = ((long long) ans * (i + 1)) % MOD;
  return ans;
}

int main(int argc, char *argv[]){
  int T; 
  int points[MAXN], P;
  scanf("%d", &T);
  while(T--){
    scanf("%d", &N);
    REP(i, N) scanf("%d%d", X+i, Y+i);
    REP(i, N) REP(j, N) if(i != j){
      int dx = X[i] - X[j], dy = Y[i] - Y[j];
      int g = gcd(dx, dy);
      dx /= g;
      dy /= g;
      if(dx <= 0 || (dx == 0 && dy < 0)){
        dx *= -1;
        dy *= -1;
      }
      a[i][j] = dy * 1000 + dx;
    }
    REP(i, 1 << N){
      colinear[i] = true;
      int first = -1, second = -1;
      REP(j, N) if(i & (1 << j)){
        if(first == -1){ first = j; continue; }
        if(second == -1){ second = j; continue; }
        if(a[first][second] != a[first][j]){ colinear[i] = false; break; }
      }
    }
    REP(i, 1 << N){
      dp2[i] = -1;
      P = 0;
      REP(j, N) if(i & (1 << j)) points[P++] = j;
      if(P < 3){ dp1[i] = (P != 0); continue; }
      dp1[i] = N;
      int first = points[0];
      FOR(j, 1, P - 1){
        int second = points[j];
        int ii = i ^ (1 << first) ^ (1 << second);
        FOR(k, j+1, P - 1) if(a[first][second] == a[first][points[k]]) ii ^= (1 << points[k]);
        dp1[i] = min(dp1[i], dp1[ii] + 1);
      }
    }
    int ans1 = dp1[(1 << N) - 1];
    int ans2 = ((long long)get((1 << N) - 1) * fac(ans1)) % MOD;
    printf("%d %d\n", ans1, ans2);
  }
  return 0;
}

Points in a Plane C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;


namespace PointsOnPlane
{
    class PointsOnPlane
    {
                public PointsOnPlane() { masks = init_masks(); vpos = init_vpos(); }

        public int[] GetSolution(int[][] points) { 
            init_sets(points);
            return find_solution(points.Length);
        }

        private void init_sets(int[][] points) {
            Array.Sort(points, Comparer<int[]>.Create(comp));
            int n = points.Length;
            int[,] subsets = new int[n, n];
            List<int> setids = new List<int>();
            for (int i = 0; i < n; ++i) {
                setids.Add(encodeset(i, 0));
                int baseid = subsets[i, i] = setids.Count;
                for (int j = i + 1; j < n; ++j) {
                    int[] p1 = new int[2] { points[j][0] - points[i][0], points[j][1] - points[i][1] };
                    bool isfound = false;
                    for (int k = (i != 0) ? 0 : 1; k < j; k += (k + 1 != i) ? 1 : 2) {
                        int[] p2 = new int[2] { points[k][0] - points[i][0], points[k][1] - points[i][1] };
                        isfound = (p1[0] * p2[1] - p1[1] * p2[0]) == 0;
                        if (isfound) {
                            subsets[i, j] = subsets[j, i] = subsets[i, k];
                            setids[subsets[i, j] - 1] = encodeset(j, setids[subsets[i, j] - 1]);
                            break;
                        }
                    }
                    if (isfound == false) {
                        setids.Add(encodeset(j, setids[baseid - 1]));
                        subsets[i, j] = subsets[j, i] = setids.Count;
                    }
                }
            }

            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    subsets[i, j] = setids[subsets[i, j] - 1];

            dp = new long[1 << n, 2];
            for (int i = 1; i < dp.GetLength(0); ++i) { dp[i, 0] = prime; dp[i, 1] = 0; }
            dp[0, 1] = 1;
            for (int i = 1; i < dp.GetLength(0); ++i) {
                var dpv = new List<int>();
                var posv = vpos[i];
                var m0 = 1 << posv[0];
                foreach (var j in posv) {
                    int seg = i & subsets[posv[0], j] & ((1 << (j + 1)) - 1);
                    dpv.Add((int)dp[i ^ seg, 0] + 1);
                }
                dp[i, 0] = dpv.Min();
            }

            sets = new List<int>[n];
            for (int i = 0; i < n; ++i) sets[i] = new List<int>();
            int mask = (1 << n) - 1;
            int minH = (int)dp[mask, 0];
            for (int i = 0; i < mask; i++) {
                int j = (mask ^ i);
                int k = subsets[vpos[j][0], vpos[j].Last()] & j;
                if (((k | i) == mask) && (dp[i, 0] == minH - 1)) sets[vpos[j][0]].Add(j);
            }
        }

        private int[] find_solution(int n)
        {
            int mainset = (1 << n) - 1;
            subsolution(mainset);
            return new int[2] { (int)dp[mainset, 0], (int)dp[mainset, 1] };
        }

        private long subsolution(int set) {
            if (dp[set, 1] > 0) return dp[set, 1];

            var subsets = new HashSet<int>();
            foreach (var el in sets[vpos[set][0]]) {
                int subset = el & set;
                if (dp[set, 0] == dp[subset ^ set, 0] + 1) subsets.Add(subset);
            }

            foreach (var subset in subsets) { dp[set, 1] = (dp[set, 1] + (dp[set, 0] * subsolution(subset ^ set)) % prime) % prime; }
            return dp[set, 1];
        }

        private static int[,] init_masks() {
            int[,] _masks = new int[maxlen, 4];
            for (int i = 1; i < maxlen; ++i) {
                for (int j = 0; (_masks[i, 0] & i) == 0; ++j) _masks[i, 0] = 1 << j;
                for (int j = maxlen; (_masks[i, 1] & i) == 0; _masks[i, 1] = 1 << (--j)) ;
                _masks[i, 2] = (~(_masks[i, 0] - 1)) & ((_masks[i, 1] << 1) - 1);
                _masks[i, 3] = fndcnt(i);
            }
            return _masks;
        }

        private static int[][] init_vpos() {
            int[][] _vpos = new int[maxlen][];
            for (int i = 0; i < maxlen; ++i) {
                var tmp = new List<int>();
                for (int j = 0; j < 16; ++j) if(((1 << j) & i) != 0) tmp.Add(j);
                _vpos[i] = tmp.ToArray();
            }
            return _vpos;
        }

        private static int fndcnt(int id) {
            int cnt = 0;
            for (; id != 0; cnt += 1 & id, id >>= 1) ;
            return cnt;
        }

        private Comparison<int[]> comp = (x1, x2) => x1[0] < x2[0] ? -1 : (x1[0] == x2[0]) && (x1[1] < x2[1]) ? -1 : 1;
        private int encodeset(int i, int setid) => setid | (1 << i);

        private static int[,] masks = null;
        private readonly int[][] vpos = null;
        private List<int>[] sets = null;
        private long[,] dp = null;
        private const long prime = 1000000007;
        private const int maxlen = 0x00010000;

        static void Main(string[] args)
        {
            TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

            int t = Convert.ToInt32(Console.ReadLine());

            var res = new PointsOnPlane();

            for (int tItr = 0; tItr < t; tItr++) {
                int n = Convert.ToInt32(Console.ReadLine());

                int[][] coordinates = new int[n][];

                for (int coordinatesRowItr = 0; coordinatesRowItr < n; coordinatesRowItr++) {
                    coordinates[coordinatesRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), coordinatesTemp => Convert.ToInt32(coordinatesTemp));
                }

                int[] result = res.GetSolution(coordinates);

                textWriter.WriteLine(string.Join(" ", result));
            }

            textWriter.Flush();
            textWriter.Close();
        }
    }
}

Points in a Plane Java Solution

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    static int MOD = 1000000007;
    
    static int maxN = 16;
    static int n;
    static boolean[][][] tri;
    static int[][] setPointsInLine = new int[maxN][maxN];
    static int[][] noPointsInLine = new int[maxN][maxN];
    static int[] memoMinMap;
    static int[][] memoVarMap;
    
    static long[][] C = new long[maxN+1][maxN+1];
    static int[][] mapPoints = new int[1 << maxN+1][];
    
    static int[][] resultNCP = new int[maxN+1][];
    static int colPoints = 0;
    
    static {
        C[0][0] = 1;
        C[1][0] = 1;
        C[1][1] = 1;
        for (int i = 2; i <= maxN; ++i) {
            C[i][0] = 1;
            for (int j = 1; j <= 3; ++j) {
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
            }
        }    
        
        for (int i = 1; i <= maxN; ++i) {
            resultNCP[i] = getResultNCP(i);
        }
        
        for(int setPoints = 0;setPoints < (1 << maxN+1);setPoints++) {
            int[] ans = new int[maxN+1];
            int k = 0;
            for(int i = 0;i < maxN;i++) {
                if(((1 << i) & setPoints) > 0) {
                    ans[++k] = i;                
                }
            }
            ans[0] = k;
            mapPoints[setPoints]= ans;
        }        

    }
    
    static int[] pointsInPlane(int[][] coordinates) {
        tri = new boolean[maxN][maxN][maxN];
        memoMinMap = new int[1 << (maxN+1)];
        Arrays.fill(memoMinMap, -1);
        memoVarMap = new int[9][];
        colPoints = 0;
        for(int i = 1;i <= 8;i++) {
            memoVarMap[i] =  new int[1 << (maxN+1)];
            Arrays.fill(memoVarMap[i], -1);
        }
        int maxCP = 2;
        for(int i = 0;i < n;i++) {
            int xi = coordinates[i][0];
            int yi = coordinates[i][1];
            for(int j = i+1;j < n;j++) {
                int lineP = 0;
                int noP = 2;
                int xj = coordinates[j][0];
                int yj = coordinates[j][1];
                for(int k = j+1;k < n;k++) {
                    int xk = coordinates[k][0];
                    int yk = coordinates[k][1];
                    if((yk-yi) * (xj-xi) == (yj-yi) * (xk-xi)) {
                        tri[i][j][k] = true;
                        lineP += (1 << k);
                        noP++;
                    }
                }
                if(maxCP < noP) {
                    maxCP = noP;
                }
                setPointsInLine[i][j] = lineP;
                noPointsInLine[i][j] = noP;
                if(lineP != 0) {
                    colPoints = colPoints | lineP;
                }
            }            
        }
        colPoints = ~colPoints;
        if(maxCP == 2) {            
            return resultNCP[n];
            
        }
        int noMin = calcMin((1 << n) - 1);
        int noVar = calcV((1 << n) - 1, 1, noMin, n);
        return new int[] {noMin, noVar};
    }

    private static int[] getResultNCP(int nNCP) {
        if(nNCP % 2 == 0) {
            int noMin = nNCP/2;
            long noV = 1;
            for(int k = nNCP;k >=4;k=k-2) {
                noV = noV * C[k][2];
            }
            return new int[] {noMin, (int) (noV % MOD)};
        }else {
            int noMin = nNCP/2+1;
            long noV = 0;
            for(int k = nNCP;k>=1;k=k-2) {
                long p = 1;
                for(int i = nNCP;i > k;i=i-2) {
                    p = p*C[i][2];
                }
                p = p*k;
                for(int i = k-1;i >=4;i=i-2) {
                    p = p*C[i][2];
                }
                noV = (noV+p) % MOD;
            }
            return new int[] {noMin, (int)noV};
        }
    }

    private static int calcV(int setPoints, int itr, int noMin, int nP) {
        if(itr == noMin+1 && setPoints != 0) {
            return 0;
        }
        if(itr == noMin+1 && setPoints == 0) {
            return 1;
        }else {
            int ans = memoVarMap[itr][setPoints];
            if(ans >= 0) {
                return ans; 
            }
            int ncp = colPoints & setPoints;
            if(ncp == setPoints) {
                ans = (int) Math.ceil(nP/2.);
                if(ans > noMin-itr+1) {
                    memoVarMap[itr][setPoints] = 0;
                    return 0;
                } else {
                    int pR = resultNCP[nP][1];
                    memoVarMap[itr][setPoints] =  pR;
                    return pR;                    
                }
            }
            ans = memoMinMap[setPoints];
            if(ans >= 0) {
                if(ans > noMin-itr+1) {
                    memoVarMap[itr][setPoints] = 0;
                    return 0;
                } else {
                    if(nP % 2 == 1 && ans == nP/2+1) {
                        int pR = resultNCP[nP][1];
                        memoVarMap[itr][setPoints] = pR;
                        return pR;
                    }
                }
            }
            int[] points = mapPoints[setPoints];
            int size = points[0];
            ans  = 0;
            Set<Integer> set = new HashSet<Integer>();
            if(size <= 2) {
                memoVarMap[itr][setPoints] =  1;
                return 1;
            }
            if(size == 3 && itr==noMin && tri[points[1]][points[2]][points[3]]) {
                memoVarMap[itr][setPoints] = 1;
                return 1;
            }
            if(size == 3 && itr==noMin-1 && !tri[points[1]][points[2]][points[3]]) {
                memoVarMap[itr][setPoints] = 6;
                return 6;
            }            
            if(size == 4) {
                if(itr==noMin-1) {
                    if(!hasCP(points)) {
                        memoVarMap[itr][setPoints] = 6;
                        return 6;
                    }else {
                        memoVarMap[itr][setPoints] = 8;
                        return 8;
                    }
                }else if(itr == noMin && colP(points)) {
                    //c++;
                    memoVarMap[itr][setPoints] = 1;
                    return 1;
                } else {
                    memoVarMap[itr][setPoints] = 0;
                    return 0;
                }
            }
            for(int i = 1;i <= size;i++) {
                int pi = points[i];
                int nextP = setPoints - (1 << pi);
                ans = (ans + calcV(nextP, itr+1, noMin, nP-1)) % MOD;
                for(int j = i+1;j <= size;j++) {
                    int pj = points[j];
                    int start = setPoints - (1 << pi) - (1 << pj);
                    int newSetPoints = setPointsInLine[pi][pj] & start;
                    if(newSetPoints == 0) {
                        ans = (ans + calcV(start, itr+1, noMin, nP-2)) % MOD;
                        continue;
                    }
                    int[] pointsLine = mapPoints[newSetPoints];
                    int pSize = pointsLine[0];
                    for (int s = 0; s < (1 << pSize); s++){ 
                        nextP = start;
                        int aP = 0;
                        for (int t = 0; t < pSize; t++) {
                            int pt1 = pointsLine[t+1];
                            if ((s & (1 << t)) > 0 && tri[pi][pj][pt1]) {
                                nextP -= (1 << pt1);
                                aP++;
                            }
                        }
                        if(set.contains(nextP)) {
                            continue;
                        }
                        set.add(nextP);
                        ans = (ans + calcV(nextP, itr+1, noMin, nP-2-aP)) % MOD;
                    }                    
                }
            }
            memoVarMap[itr][setPoints] = ans;
            return ans;
        }
    }

    private static boolean colP(int[] points) {
        int p1 = points[1];
        int p2 = points[2];
        int p3 = points[3];
        int p4 = points[4];
        return tri[p1][p2][p3] && tri[p1][p2][p4];
    }

    private static boolean hasCP(int[] points) {
        int p1 = points[1];
        int p2 = points[2];
        int p3 = points[3];
        int p4 = points[4];
        return tri[p1][p2][p3] || tri[p1][p2][p4] || tri[p2][p3][p4] || tri[p1][p3][p4];
    }

    private static int calcMin(int setPoints) {
        if(setPoints == 0) {
            return 0;
        }else {
            int ans = memoMinMap[setPoints];
            if(ans >= 0) {
                return ans; 
            }
            int[] points = mapPoints[setPoints];
            int size = points[0];
            int ncp = colPoints & setPoints;
            if(ncp == setPoints) {
                ans = (int) Math.ceil(size/2.);
                memoMinMap[setPoints] = ans;
                return ans;
            }
            if(size <= 2) {
                memoMinMap[setPoints] = 1;
                return 1;
            }
            if(size == 3) {
                if(tri[points[1]][points[2]][points[3]]) {
                    memoMinMap[setPoints] = 1;
                    return 1;
                }else {
                    memoMinMap[setPoints] = 2;
                    return 2;
                }
                
            }
            if(size == 4) {
                int p1 = points[1];
                int p2 = points[2];
                int p3 = points[3];
                int p4 = points[4];
                if(tri[p1][p2][p3] && tri[p1][p2][p4]) {                
                    memoMinMap[setPoints] = 1;
                    return 1;
                } else {
                    memoMinMap[setPoints] = 2;
                    return 2;
                }
            }
            int min = 10;
            for(int i = 1;i <= size;i++) {
                for(int j = i+1;j <= size;j++) {
                    int nextP = (setPoints - (setPoints & (setPointsInLine[points[i]][points[j]] + (1 << points[i]) + (1 << points[j])))); 
                    ans = 1+calcMin(nextP);
                    if(ans < min) {
                        min = ans;
                    }
                }
            }
            memoMinMap[setPoints] = min;
            return min;
        }        
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

        for (int tItr = 0; tItr < t; tItr++) {
            n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

            int[][] coordinates = new int[n][2];

            for (int coordinatesRowItr = 0; coordinatesRowItr < n; coordinatesRowItr++) {
                String[] coordinatesRowItems = scanner.nextLine().split(" ");
                scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

                for (int coordinatesColumnItr = 0; coordinatesColumnItr < 2; coordinatesColumnItr++) {
                    int coordinatesItem = Integer.parseInt(coordinatesRowItems[coordinatesColumnItr]);
                    coordinates[coordinatesRowItr][coordinatesColumnItr] = coordinatesItem;
                }
            }

            int[] result = pointsInPlane(coordinates);

            for (int resultItr = 0; resultItr < result.length; resultItr++) {
                bufferedWriter.write(String.valueOf(result[resultItr]));

                if (resultItr != result.length - 1) {
                    bufferedWriter.write(" ");
                }
            }

            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Points in a Plane JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

const LOG = false//true
const MODULO = 1000000007


function computeSlope(p,c) {
    var slope
    var dx = p[0] - c[0]
    if(dx === 0) {
        slope = 'y'
    }else{
        var dy = p[1] - c[1]
        slope = 100*dy/dx + '%'
    }
    return slope
}

/*
 * Complete the pointsInPlane function below.
 */
function pointsInPlane(coordinates) {
    /*
     * Write your code here.
     */

    cache = {}

    var remaining = (1 << coordinates.length) - 1

    var result = solve(coordinates, remaining)

    for(var i = 2; i <= result[0]; i++) {
        result[1] = (result[1] * i) % MODULO
    }

    return result
}

function getFirstIndex(remaining, fromIndex = 0) {
    remaining = remaining >> fromIndex
    while(true) {
        if(remaining & 0x1) {
            return fromIndex
        }
        fromIndex++
        remaining = remaining >> 1
    }
}

function applySelection(i, slopeIndexes) {
    var result = 0;
    var slopeIndex = 0;
    
    while(i) {
        if(i & 0x1) {
            var index = slopeIndexes[slopeIndex]
            //take that index
            result |= 1 << index
        }
        i = i >> 1
        slopeIndex++
    }

    return result
}

var cache = {}

function solve(coordinates, remaining) {
    if(!remaining) { 
        var r = [0, 1]
        if(LOG) console.log('solve: ' + remaining.toString(2) ) 
        if(LOG) console.log('  -->  ' + logResult(r))

        return r
    }

    if(cache[remaining]){
        return cache[remaining]
    }

    var index = getFirstIndex(remaining);
    var p = coordinates[index]

    var slopes = {}

    for(var i = index+1; i < coordinates.length; i++) {
        if((remaining >> i) & 0x1) {
            var c = coordinates[i]
            var slope = computeSlope(p, c)
            slopes[slope] = (slopes[slope] || {
                count: 0,
                indexes: []
            })
            slopes[slope].count++;
            slopes[slope].indexes.push(i)
        }
    }

    if(LOG) console.log('solving: ' + remaining.toString(2) ) 
    if(LOG) console.log('slopes: ', slopes)

    var results = []

    // just remove p alone and then solve the rests
    if(LOG) console.log('only remove: ' + (1 << index).toString(2))
    results.push(removeAndSolve(1 << index, coordinates, remaining, index + 1))

    Object.keys(slopes).forEach(slopeKey => {
        var slope = slopes[slopeKey]
        var possibilities = (1 << slope.count) - 1
        for(var i = 1; i <= possibilities; i++) {
            var selected = applySelection(i, slope.indexes)
            if(LOG) console.log('remove on same slope: ' + selected.toString(2))
            results.push(removeAndSolve((1 << index) + selected, coordinates, remaining))
        } 
    })

    if(LOG) console.log('solve: ' + remaining.toString(2) ) 
    var result = mergeResults(results)

    cache[remaining] = result

    return result
}

function removeAndSolve(toRemove, coordinates, remaining) {
    remaining -= toRemove;
    return solve(coordinates, remaining)
}

function mergeResults(results) {
    if(LOG) console.log('mergeResults: ') 
    if(LOG) {
        results.forEach(result => {
            console.log(' ' + logResult(result))
        })
    }

    var minResult = [Infinity, Infinity]
    results.forEach(result => {
        if(result[0] < minResult[0]) {
            minResult = [result[0], 0]
        }
        if(result[0] === minResult[0]) {
            minResult[1] = (minResult[1] + result[1]) % MODULO
        }
    })

    // add this step's turn
    minResult[0]++

    if(LOG) console.log('  -->  ' + logResult(minResult))
    return minResult
}

function logResult(result) {
    return '' + result[0] + ' - ' + result[1] + ' ways'
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const n = parseInt(readLine(), 10);

        let coordinates = Array(n);

        for (let coordinatesRowItr = 0; coordinatesRowItr < n; coordinatesRowItr++) {
            coordinates[coordinatesRowItr] = readLine().split(' ').map(coordinatesTemp => parseInt(coordinatesTemp, 10));
        }

        let result = pointsInPlane(coordinates);

        ws.write(result.join(" ") + "\n");
    }

    ws.end();
}

Points in a Plane C Solution

Points in a Plane C++ Solution

Points in a Plane C Sharp Solution

Points in a Plane Java Solution

Points in a Plane JavaScript Solution

Related Posts