#include #include #include #include #include #include #include #include #include #include using namespace std; const int64_t INF = 1e18; typedef vector VL; struct MCMF { int N; vector> ed, red; vector cap, flow, cost; vector seen; VL dist, pi; vector> par; MCMF(int N) : N(N), ed(N), red(N), cap(N, VL(N)), flow(cap), cost(cap), seen(N), dist(N), pi(N), par(N) {} void addEdge(int from, int to, int64_t cap, int64_t cost) { this->cap[from][to] = cap; this->cost[from][to] = cost; ed[from].push_back(to); red[to].push_back(from); } void path(int s) { fill(seen.begin(), seen.end(), 0); fill(dist.begin(), dist.end(), INF); dist[s] = 0; int64_t di; priority_queue> q; q.push({0, s}); auto relax = [&](int i, int64_t cap, int64_t cost, int dir) { int64_t val = di - pi[i] + cost; if (cap && val < dist[i]) { dist[i] = val; par[i] = {s, dir}; q.push({-dist[i], i}); } }; while (!q.empty()) { s = q.top().second; q.pop(); if(seen[s]) continue; seen[s] = 1; di = dist[s] + pi[s]; for(auto i: ed[s]) if (!seen[i]) relax(i, cap[s][i] - flow[s][i], cost[s][i], 1); for(auto i: red[s]) if (!seen[i]) relax(i, flow[i][s], -cost[i][s], 0); } for(int i = 0; i < N; i++) pi[i] = min(pi[i] + dist[i], INF); } pair maxflow(int s, int t) { int64_t totflow = 0, totcost = 0; while (path(s), seen[t]) { int64_t fl = INF; for (int p,r,x = t; tie(p,r) = par[x], x != s; x = p) fl = min(fl, r ? cap[p][x] - flow[p][x] : flow[x][p]); totflow += fl; for (int p,r,x = t; tie(p,r) = par[x], x != s; x = p) if (r) flow[p][x] += fl; else flow[x][p] -= fl; } for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) totcost += cost[i][j] * flow[i][j]; return {totflow, totcost}; } }; template struct Point3D { typedef Point3D P; typedef const P& R; T x, y, z; explicit Point3D(T x=0, T y=0, T z=0) : x(x), y(y), z(z) {} bool operator<(R p) const { return tie(x, y, z) < tie(p.x, p.y, p.z); } bool operator==(R p) const { return tie(x, y, z) == tie(p.x, p.y, p.z); } P operator+(R p) const { return P(x+p.x, y+p.y, z+p.z); } P operator-(R p) const { return P(x-p.x, y-p.y, z-p.z); } P operator*(T d) const { return P(x*d, y*d, z*d); } P operator/(T d) const { return P(x/d, y/d, z/d); } T dot(R p) const { return x*p.x + y*p.y + z*p.z; } P cross(R p) const { return P(y*p.z - z*p.y, z*p.x - x*p.z, x*p.y - y*p.x); } T dist2() const { return x*x + y*y + z*z; } double dist() const { return sqrt((double)dist2()); } //Azimuthal angle (longitude) to x-axis in interval [-pi, pi] double phi() const { return atan2(y, x); } //Zenith angle (latitude) to the z-axis in interval [0, pi] double theta() const { return atan2(sqrt(x*x+y*y),z); } P unit() const { return *this/(T)dist(); } //makes dist()=1 //returns unit vector normal to *this and p P normal(P p) const { return cross(p).unit(); } //returns point rotated 'angle' radians ccw around axis P rotate(double angle, P axis) const { double s = sin(angle), c = cos(angle); P u = axis.unit(); return u*dot(u)*(1-c) + (*this)*c - cross(u)*s; } }; typedef Point3D P; void normalize(P& dir) { int64_t scale = 0; scale = gcd(scale, dir.x); scale = gcd(scale, dir.y); scale = gcd(scale, dir.z); scale = abs(scale); dir.x /= scale; dir.y /= scale; dir.z /= scale; } bool sameDir(const P& a, const P& b) { P x = a.cross(b); if(x.x) return false; if(x.y) return false; if(x.z) return false; return true; } bool isOnLine(const P& s, const P& e, const P& p) { return sameDir(p-s, e-s); } bool collinear(const vector

& locs) { if(locs.size() <= 2) return true; P desiredDir = (locs[1] - locs[0]); normalize(desiredDir); for(int i = 2; i < locs.size(); i++) { if(!isOnLine(locs[0], locs[1], locs[i])) return false; } return true; } bool rayIntersect(P v1, P d1, P v2, P d2) { assert(!(v1 == v2)); if(d1 == d2) return false; // v1 + d1 * t_1 == v2 + d2 * t_2 // v1.x + d1.x * t_1 == v2.x + d2.x * t_2 // d1.x * t_1 - d2.x * t_2 == v2.x - v1.x // d1.y * t_1 - d2.y * t_2 == v2.y - v1.y int64_t a1 = d1.x; int64_t b1 = -d2.x; int64_t c1 = v2.x - v1.x; int64_t a2 = d1.y; int64_t b2 = -d2.y; int64_t c2 = v2.y - v1.y; int64_t t1num = c1*b2-b1*c2; int64_t t2num = a1*c2-c1*a2; int64_t denom = a1*b2-a2*b1; if(denom < 0) { denom *= -1; t1num *= -1; t2num *= -1; } if(denom == 0) return false; // ??? if(t1num < 0 || t2num < 0) return false; return v1*denom + d1*t1num == v2*denom + d2*t2num; } int main() { int n; cin >> n; if(n==1) { cout << "-1\n"; return 0; } vector

locs(n), dirs(n); map loctoidx; for(int i = 0; i < n; i++) { cin >> locs[i].x >> locs[i].y >> locs[i].z; cin >> dirs[i].x >> dirs[i].y >> dirs[i].z; loctoidx[locs[i]] = i; normalize(dirs[i]); } vector> seeing(n); // seeing[i][j] means i sees j vector> secondseeing(n); vector> canSee(n); // canSee[i][j] means i can see j with some rotation auto initseeing = [&]() -> void { for(int i = 0; i < n; i++) loctoidx[locs[i]] = i; for(int i = 0; i < n; i++) { seeing[i].assign(n, false); canSee[i].assign(n, false); secondseeing[i].assign(n, false); map> dirtoclosest; for(int j = 0; j < n; j++) { if(i == j) continue; P dir = locs[j] - locs[i]; normalize(dir); int64_t dist = (locs[j] - locs[i]).dist2(); dirtoclosest[dir].push_back(locs[j]); } for(auto& [k, v]: dirtoclosest) { sort(v.begin(), v.end(), [&](P a, P b) -> bool { return (a-locs[i]).dist2() < (b-locs[i]).dist2(); }); canSee[i][loctoidx[v[0]]] = true; } P actualdir = dirs[i]; if(dirtoclosest.count(actualdir)) { vector

& cand = dirtoclosest[actualdir]; seeing[i][loctoidx[cand[0]]] = true; if(cand.size() >= 2) secondseeing[i][loctoidx[cand[1]]] = true; } } }; if(n%2 && collinear(locs)) { Point3D lineDir = locs[1] - locs[0]; { // sort all normalize(lineDir); vector ord(n); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int a, int b) -> bool { return lineDir.dot(locs[a] - locs[0]) < lineDir.dot(locs[b] - locs[0]); }); { vector

nlocs = locs; vector

ndirs = dirs; for(int i = 0; i < n; i++) { nlocs[i] = locs[ord[i]]; ndirs[i] = dirs[ord[i]]; loctoidx[nlocs[i]] = i; } locs.swap(nlocs); dirs.swap(ndirs); } } int ret = 1000 + n; for(int q = 0; q < 2; q++) { initseeing(); for(int i = 0; i < n; i++) { // move i out vector cands; for(int j = 0; j < n; j++) if(i != j) cands.push_back(j); vector> dp(cands.size() + 1, {(int)1e9, (int)1e9}); dp[0] = {1000, 2000}; auto cansee = [&](int a, int b) -> bool { if(a == i || b == i) return false; if(seeing[a][b]) return true; if(seeing[a][i] && secondseeing[a][b]) return true; return false; }; for(int j = 0; j < cands.size(); j += 2) { int a = cands[j]; int b = cands[j+1]; dp[j+2][0] = min(dp[j+2][0], dp[j][0] + !cansee(a, b) + !cansee(b, a)); dp[j+2][1] = min(dp[j+2][1], dp[j][1] + !cansee(a, b) + !cansee(b, a)); // boring two case { bool bLine = sameDir(dirs[b], lineDir); bool iLine = sameDir(dirs[i], lineDir); if(bLine && iLine) dp[j+2][1] = min(dp[j+2][1], dp[j][0] + !cansee(a, b) + 2); else { if(bLine || iLine || !rayIntersect(locs[b], dirs[b], locs[a], dirs[i] * -1)) dp[j+2][1] = min(dp[j+2][1], dp[j][0] + !cansee(a, b) + 1); else dp[j+2][1] = min(dp[j+2][1], dp[j][0] + !cansee(a, b)); } } // interesting big casea { int numturns = !cansee(a, b); for(int nj = j + 2; nj < cands.size(); nj += 2) { numturns += !cansee(cands[nj-1], cands[nj]); int na = cands[nj]; int nb = cands[nj+1]; bool bLine = sameDir(dirs[nb], lineDir); bool iLine = sameDir(dirs[i], lineDir); if(bLine && iLine) dp[nj+2][1] = min(dp[nj+2][1], dp[j][0] + numturns + !cansee(na, nb) + 2); else { if(bLine || iLine || !rayIntersect(locs[nb], dirs[nb], locs[a], dirs[i] * -1)) dp[nj+2][1] = min(dp[nj+2][1], dp[j][0] + numturns + !cansee(na, nb) + 1); else dp[nj+2][1] = min(dp[nj+2][1], dp[j][0] + numturns + !cansee(na, nb)); } numturns += !cansee(na, nb); } } } ret = min(ret, dp.back()[1]); } reverse(locs.begin(), locs.end()); reverse(dirs.begin(), dirs.end()); } cout << ret << "\n"; } else { initseeing(); MCMF mcmf(2*n+2); for(int i = 0; i < n; i++) { assert(!canSee[i][i]); for(int j = 0; j < n; j++) { if(seeing[i][j]) { mcmf.addEdge(i, n+j, 1, 0); } else if(canSee[i][j]) { mcmf.addEdge(i, n+j, 1, 1); } } mcmf.addEdge(2*n, i, 1, 0); mcmf.addEdge(i+n, 2*n+1, 1, 0); } cout << mcmf.maxflow(2*n, 2*n+1).second << "\n"; } }