点と線分の距離 ~long double VER~

// #define EPS (1e-14)
#define EPS (1e-12)
#define equals(a,b) (fabs((a)-(b)) < EPS)

code (library)

typedef complex<ld> C;

// 2点を与えると ax + by = c なる(a,b,c)を返します
VI get_a_b_c_from_two_points(C p, C q){
  ll x1=p.real();
  ll y1=p.imag();
  ll x2=q.real();
  ll y2=q.imag();
  ll a = y1-y2;
  ll b = x2-x1;
  ll c = y1*(x2-x1)-x1*(y2-y1);
  return {a,b,c};
}

// 外積
ld cross(C a, C b){
  return a.real()*b.imag() - a.imag()*b.real();
}

// 内積
ld dot(C a, C b){
  return a.real() * b.real() + a.imag() * b.imag();
}

// ベクトルの長さ
ld length(C v){
  return sqrt(v.real()*v.real() + v.imag()*v.imag());
}

// 2点間の距離
ld distance_between_two_points(C a, C b){
  return length(a-b);
}

// 単位ベクトル
C unit_vector(C v){
  return v / length(v);
}

// 点pを点a,bからなる直線に射影した点を返す
C point_projection_to_line(C p, C a, C b){
  C v = b-a;
  C u = unit_vector(v);
  C AP = p - a;
  // APをuに射影
  ld len = dot(AP, u);
  return a + u*len;
}

// 2点がほぼ同じ位置か
bool is_same_position(C a, C b){
  ld d = distance_between_two_points(a,b);
  if(equals(d,0))return true;
  return false;
}

// 2つのベクトルが平行か
bool is_parallel(C v, C w){
  ld area = cross(v,w);
  if(equals(area,0))return true;
  return false;
}

// 点pが線分a,bの間にいるか(接するのも含む)
bool is_in_segment(C p, C a, C b){
  if(is_same_position(p,a))return true;
  if(is_same_position(p,b))return true;
  // 平行でないならありえない
  auto pa = a-p;
  auto pb = b-p;
  if(!is_parallel(pa,pb))return false;
  // 以降、平行
  if(dot(pa,pb)<0)return true;
  return false;
}

// 点pと線分a,bの距離
ld distance_point_to_segment(C p, C a, C b){
  ld mi = inf;
  chmin(mi, distance_between_two_points(p,a));
  chmin(mi, distance_between_two_points(p,b));
  C q = point_projection_to_line(p,a,b);
  if(is_in_segment(q,a,b)){
    chmin(mi, distance_between_two_points(p,q));
  }
  return mi;
}

// 線分が交差するか
// ベクトル p0->p1, q0->q1
// https://perogram.hateblo.jp/entry/is_intersect
bool is_intersect(C p0, C p1, C q0, C q1){

  {
    // 同じ点があるなら交差
    if(p0==p1)return true;
    if(p0==q0)return true;
    if(p0==q1)return true;
    if(p1==q0)return true;
    if(p1==q1)return true;
    if(q0==q1)return true;
  }

  bool is_parallel = false;
  {
    C v = p0-p1;
    C w = q0-q1;
    if(cross(v,w)==0) is_parallel=true;
  }

  if(is_parallel){
    // 包含・重なり・ギリギリ接触を交差とする
    if(is_in_segment(p0,q0,q1))return true;
    if(is_in_segment(p1,q0,q1))return true;
    if(is_in_segment(q0,p0,p1))return true;
    if(is_in_segment(q1,p0,p1))return true;
    return false;
  }

  // 以降、平行ではないとする

  // p側から見た交差チェック
  auto v0 = p1 - p0;
  auto v1 = q0 - p0;
  auto v2 = q1 - p0;
  if(cross(v0, v1) * cross(v0, v2) > 0){
      return false;
  }
  // q側から見た交差チェック
  v0 = q1 - q0;
  v1 = p0 - q0;
  v2 = p1 - q0;
  if(cross(v0, v1) * cross(v0, v2) > 0){
      return false;
  }
  return true;
}

他人のライブラリ

2つの線分の交点の位置 ~ax + by = cと逆行列~

f:id:peroon:20200924230155p:plain

  • その他
    • 未だに交点を求めていなかったとは...
    • 書き捨てクオリティになっているので幾何ライブラリは整備したい...

スライド最小値 Sliding Window Minimum Algorithm

  • Quiz
  • AC
  • 解説
    • 蟻本p301にある
    • 最初はmultisetを使ってO(NlogN)で解いたが、スライド最小値を使うとO(N)となる
      • (N=1000000なのでNlogNだと2x107となり各テストケース0.2秒かかりうるので遅さを感じた)
    • dequeを使い、範囲Lの中で最小のインデックスがdequeの左端にあることを維持すればよい
    • 範囲内のインデックスであっても使わないことが確定しているものは早期に捨てる(while内でpop_backしている箇所)
int main(){
    // input
    ll N,L;
    cin>>N>>L;

    VI A(N);
    rep(i, N) cin >> A[i];

    deque<ll> que;
    que.push_back(0);
    FOR(i,1,L){
      while(que.size()>0 && A[que.back()]>=A[i]){
        que.pop_back();
      }
      que.push_back(i);
    }
    VI Ans;
    Ans.push_back(A[que.front()]);
    
    FOR(i,L,N){
      // 新しく足すのがA[i]

      if(que.front()==i-L) que.pop_front(); // 範囲外なので除去

      // A[i]を足す
      while(que.size()>0 && A[que.back()]>=A[i]){
        que.pop_back();
      }
      que.push_back(i);    
      Ans.push_back(A[que.front()]);
    }
    print_vector(Ans);

    return 0;
}

英名

AOJ 2251 - Merry Christmas ~DAG上の最小パス被覆 minimum path cover~

f:id:peroon:20200924033756p:plain

#include <atcoder/maxflow>
using namespace atcoder; // 忘れがち

// 入力:DAGなグラフG
// 出力:最小パス被覆
ll minimum_path_cover(VV& G){
  ll N = SZ(G);
  ll source = 2*N;
  ll sink = 2*N+1;
  mf_graph<ll> flow(2*N+2);

  rep(i,N){
    flow.add_edge(source,i,1);
    flow.add_edge(N+i,sink,1);
  }
  // 二重辺をはらないように注意
  rep(i,N){
    for(ll to : G[i]){
      flow.add_edge(i, to+N, 1);
    }
  }
  ll max_flow = flow.flow(source, sink);
  return N - max_flow;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    while(true){
      ll N,M,L;
      cin>>N>>M>>L;
      debug(N,M,L);
      if(N==0) return 0;

      auto wf = WarshallFloyd(N);
      
      // edge
      rep(i,M){
        ll a,b,c;
        cin>>a>>b>>c;
        wf.register_edge2(a,b,c);
      }
      wf.calc();

      // requests
      VI P(L);
      VI T(L);
      rep(i,L){
        cin>>P[i]>>T[i];
      }

      // リクエストiの後にリクエストjを処理できるなら辺
      // これはDAG
      VV G(L);
      rep(i,L){
        rep(j,L){
          if(i==j) continue;
          // move i to j
          ll a = P[i];
          ll b = P[j];
          ll d = wf.distance(a,b);
          if(T[i]+d<=T[j]){
            G[i].push_back(j);
          }
        }
      }

      ll ans = minimum_path_cover(G);
      p(ans);
    }
   
    return 0;
}

D: mod rally ~ACL sccを用いて強連結成分分解~

f:id:peroon:20200922101408p:plain

#include <atcoder/scc>
using namespace atcoder; // 忘れがち

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M;
    cin>>N>>M;

    VI A(N);
    rep(i, N) cin >> A[i];

    auto g = scc_graph(M);
    FOR(i,1,M){
      for(ll a : A){
        ll to = (i*a)%M;
        if(i==to)continue;
        g.add_edge(i,to);
      }
    }

    // 強連結成分分解
    auto G = g.scc();
    ll sz = SZ(G);

    // 各頂点がどのグループに属するかのテーブル
    VI Group(M);
    rep(i,sz){
      for(ll a : G[i]) Group[a] = i;
    }

    VI dist(sz, 0);

    // トポロジカル順にDPして始点からの距離を求める
    ll ma = 0;
    rep(i,sz){
      for(ll from : G[i]){
        for(ll a : A){
          ll to = (from*a)%M;
          if(Group[from]==Group[to])continue;
          chmax(dist[Group[to]], dist[Group[from]]+1);
          chmax(ma, dist[Group[to]]);
        }
      }
    }

    if(ma==sz-1) yes();
    no();

    return 0;
}