Yandex.Algorithm 2020 Final B問題 - Catherine the developer works from home

Source

Yandex.Algorithm 2020 Final
終了後に提出できるコンテスト
問題文

問題概要

省略

解法

省略

cLay（version 20201102-1）のコード

C++に変換後のコードはこちら

int N;
ll X[1000], Y[1000];

int sz; ll dx[1d6], dy[1d6], dp1[1d6], dp2[1d6];
int ls; ll lss[1d6];
{
  ll a, b, c, d, i, j, k;
  ll res = 0;
  map<ll,int> s;
  map<pair<ll,ll>,int> ss;
  rd(N,(X,Y)(N));

  rep(i,N) rep(j,i+1,N){
    a = X[i] - X[j];
    b = Y[i] - Y[j];
    if(a < 0 || (a == 0 && b < 0)) (a, b) *= -1;
    (a, b) /= gcd(abs(a), abs(b));
    (c, d) = (X[i], Y[i]);
    if(a > 0){
      k = cDiv(-c, a);
      (c, d) += (k*a, k*b);
    } else {
      d = 0;
    }
    arrInsert(sz, sz, dx, a, dy, b, dp1, c, dp2, d);
  }

  sortA(sz, dx, dy, dp1, dp2);
  rep(i,sz){
    ls = 1;
    lss[0] = 1;
    while(i+1 < sz && dx[i]==dx[i+1] && dy[i]==dy[i+1]){
      if(dp1[i]!=dp1[i+1] || dp2[i]!=dp2[i+1]) lss[ls++] = 0;
      lss[ls-1]++;
      i++;
    }
    k = sum(lss(ls));
    res += k * (k-1) / 2;
    rep(j,ls) res -= lss[j] * (lss[j]-1) / 2;
  }

  rep(i,N) rep(j,i+1,N){
    d = (X[i] + X[j]) * (4d9 + 5) + (Y[i] + Y[j]);

    a = X[i] - X[j];
    b = Y[i] - Y[j];
    if(a < 0 || (a == 0 && b < 0)) (a, b) *= -1;
    (a, b) /= gcd(abs(a), abs(b));
    c = a * (4d9 + 5) + b;

    res -= (s[d]++);
    res += (ss[make_pair(d,c)]++);
  }
  wt(res);
}

Current time: 2024年04月27日01時20分26秒
Last modified: 2020年11月08日09時15分57秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Yandex_Algorithm
トップページに戻る

Logged in as: unknown user (not login)

ログイン：