mahmoud-a
9/9/2017 - 10:09 AM

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1949

``````#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

int getBit(int num, int indx) {
return ((num>>indx) & 1) == 1;
}

int setBit1(int num, int indx) {
return num | (1<<indx);
}

int setBit0(int num, int indx) {
return num & ~(1<<indx);
}

int cntBits(int num) {
int ret = 0;
while(num) {
if(num%2) {
ret++;

}
num/=2;
}
return ret;
}

const int MAX = 10;
const int OO = 1e9;

int n, m;
string s;
int cache[1<<16];
int X[20], Y[20];
int preprocessed[20][20];

//cout << "DEBUG :" << " " << m << endl;

return 0;
}

if(ret != -1)
return ret;
ret = OO;

vector<int> ones;
lp(i, n) {
ones.push_back(i);
}

for(int i = 0; i < sz(ones); i++) {

for(int j = i+1; j < sz(ones); j++) {
int tmpm = mask & preprocessed[ ones[i] ][ ones[j] ];
//cout << "DEBUG HERE: " << tmpm << endl;
ret = min(ret, 1+minRay(tmpm));
//cout << "HRRRRRRRRRRRRRRRRRRRRRR\n";
}
}
if(ret == OO)
return ret = 1;

return ret;
}

void preprocess() {
lp(i, n) {
for(int j = 0; j < n; j++) {
if(i != j) {
int tmpm = (1<<n)-1;
tmpm = setBit0(tmpm, i);
tmpm = setBit0(tmpm, j);
for(int k = 0; k < n ; k++) {
if(i != k && j != k) {

int x1 = X[j] - X[i];
int y1 = Y[j] - Y[i];
int x2 = X[k] - X[i];
int y2 = Y[k] - Y[i];
if(x1*y2 - x2*y1 == 0)
tmpm = setBit0(tmpm, k);
}
}
preprocessed[i][j] = tmpm;
}
}
}
}
int main() {
int t;
cin>>t;
lp(i, t) {
clr(cache, -1);
cin>>n>>m;
lp(j, n) {
cin>>X[j]>>Y[j];
}
preprocess();
cout << "Case #" << i+1 << ":\n" << minRay(mask) << "\n";
if(i != t-1)
cout << endl;
}
return 0;
}``````