In this HackerRank Points in a Plane problem solution, we have given 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) is needed to remove all the points.
- The number of ways to remove them in T turns. Two ways are considered different if any point is removed in a different turn.
Problem solution in Java.
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("(rn|[nru2028u2029u0085])*");
for (int tItr = 0; tItr < t; tItr++) {
n = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])*");
int[][] coordinates = new int[n][2];
for (int coordinatesRowItr = 0; coordinatesRowItr < n; coordinatesRowItr++) {
String[] coordinatesRowItems = scanner.nextLine().split(" ");
scanner.skip("(rn|[nru2028u2029u0085])*");
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();
}
}
Problem solution in C++.
#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: %dn", 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 %dn", ans1, ans2);
}
return 0;
}
Problem solution in C.
#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 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;
}
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(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;
}
}
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;}
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);
}
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;
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);
}
v = a[i][0][0];
for(j=2;j<=i;j++) v= (v*j)%P;
printf("%lld %lldn",i,v);
}
return 0;
}