Submission #42097253

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
ll gcd(ll a,ll b) {
  if(b<0) b=-b;
  return (b == 0)?a:gcd(b,a%b);
}
using frac=pair<ll,ll>; // {a,b} = a/b
using point=array<frac,3>;
using direct=array<frac,3>;
using line=pair<point,direct>;
const frac ZERO{0,1};

frac norm(const frac&a){
  auto [t,b]=a;
  if(t==0) return {0,1};
  if(t < 0) {
    t=-t;
    b=-b;
  }
  ll m = gcd(t,b);
  return {t/m,b/m};
}

frac operator+(const frac&a,const frac&b){
  return norm({a.first*b.second+a.second*b.first,a.second*b.second});
}
frac operator-(const frac&a,const frac&b){
  return norm({a.first*b.second-a.second*b.first,a.second*b.second});
}
frac operator*(const frac&a,const frac&b){
  return norm({a.first*b.first,a.second*b.second});
}

frac operator/(const frac&a,const frac&b){
  assert(b.first != 0);
  return norm({a.first*b.second,a.second*b.first});
}

pair<bool,array<frac,3> > cross(const line&l0,const line&l1){
  // pl(l0);
  // pl(l1);
  auto [p0,a0] = l0; // [x,y,z] = p0 + a0 t0
  auto [p1,a1] = l1; // [x,y,z] = p1 + a1 t1
  vector A(3,vector<frac>(3)); // 增广矩阵
  rep(i,0,3){
    A[i][0] = a0[i];
    A[i][1] = ZERO - a1[i];
    A[i][2] = p1[i]-p0[i];
  }
  // 高斯消元
  rep(c,0,2) { // col and row
    rep(i,c,3) if(A[i][c] != ZERO) {
      swap(A[i],A[c]);
      break;
    }
    if(A[c][c] == ZERO) return {false, {}};
    per(j,c,3) A[c][j] = A[c][j] / A[c][c]; // 单位化
    rep(i,0,3) if(i!=c) per(j,c,3) A[i][j] = A[i][j] - A[c][j] * A[i][c];
  }
  if(A[2][2] != ZERO) return {false,{}};
  frac t0 = A[0][2];
  frac x = p0[0] + t0 * a0[0];
  frac y = p0[1] + t0 * a0[1];
  frac z = p0[2] + t0 * a0[2];
  return {true,{x,y,z}};
}

int main(){
  vector<point> xyz;
  int n=read();
  rep(i,0,n) {
    frac x=norm({read(),1});
    frac y=norm({read(),1});
    frac z=norm({read(),1});
    xyz.push_back({x,y,z});
  }
  auto cmp= [&](auto &a,auto &b){
      rep(t,0,size(a)) if(a[t] != b[t]) return (a[t]-b[t]).second < 0;
      return false;
  };
  sort(begin(xyz),end(xyz),cmp);
  int ans = n;
  auto arrow=[&](const point&a,const point&b) -> direct {
    frac dx=b[0]-a[0];
    frac dy=b[1]-a[1];
    frac dz=b[2]-a[2];
    assert(dx != ZERO);
    dz = dz/dx;
    dy = dy/dx;
    dx = dx/dx;
    return {dx,dy,dz};
  };
  // 多点共线
  rep(i,0,n) rep(j,i+1,n) if(xyz[i][0] != xyz[j][0]){
    direct i2j = arrow(xyz[i],xyz[j]);
    int cnt = 2;
    rep(k,j+1,n) if(i2j == arrow(xyz[i],xyz[k])) cnt ++ ;
    ans = min(ans, n - (cnt-1));
  }
  auto count=[&](const point&p){
    int rm = 0;
    vector<direct> arrows;
    rep(i,0,n) arrows.push_back(arrow(p,xyz[i]));
    sort(begin(arrows),end(arrows),cmp);
    rep(i,1,size(arrows)) if(arrows[i] == arrows[i-1]) rm++;
    ans = min(ans,n-rm);
  };
  // 两线交点 i->j, k->l
  rep(i,0,n) rep(j,i+1,n) if(xyz[i][0] != xyz[j][0]) {
    line i2j = {xyz[i], arrow(xyz[i],xyz[j])};
    rep(k,i+1,n) if(k!=j) rep(l,k+1,n) if(l != j) if(xyz[k][0] != xyz[l][0]){
      line k2l = {xyz[k], arrow(xyz[k],xyz[l])};
      auto [ok, p] = cross(i2j,k2l);
      if(ok and p[0].second < 0) count(p);
    }
  }
  printf("%d\n",ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:6:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    6 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result