結果

問題 No.461 三角形はいくつ？
ユーザー しらっ亭しらっ亭
提出日時 2016-12-12 04:19:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 4,586 bytes
コンパイル時間 1,905 ms
コンパイル使用メモリ 183,460 KB
実行使用メモリ 100,428 KB
最終ジャッジ日時 2024-11-29 14:36:17
合計ジャッジ時間 29,326 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
65,792 KB
testcase_01 AC 48 ms
65,920 KB
testcase_02 AC 49 ms
65,920 KB
testcase_03 AC 48 ms
65,920 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 AC 1,711 ms
98,808 KB
testcase_26 AC 1,719 ms
98,800 KB
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 AC 50 ms
65,920 KB
testcase_34 AC 51 ms
65,920 KB
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define bit(n) (1LL<<(n))
#define sz(x) ((int)(x).size())
#define fst first
#define snd second
using ll=long long;using pii=pair<int,int>;
using vb=vector<bool>;using vs=vector<string>;
using vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>;
using vl=vector<ll>;using vvl=vector<vl>;using vvvl=vector<vvl>;
using vd=vector<double>;using vvd=vector<vd>;using vvvd=vector<vvd>;
using vpii=vector<pii>;using vvpii=vector<vpii>;using vvvpii=vector<vvpii>;
template<typename T>T read(){T t;cin>>t;return t;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){o<<'('<<p.fst<<", "<<p.snd<<')';return o;}

#define A first
#define B second

inline int cmp(int a, int b, int c, int d) {
  ll ad = a * d;
  ll cb = c * b;
  ll ret = ad - cb;
  if (ret > 0) return 1;
  if (ret < 0) return -1;
  return 0;
}

inline bool cmp_b(const pii &lhs, decltype(lhs) rhs) {
  return cmp(lhs.A, lhs.B, rhs.A, rhs.B) <= 0;
}

// a/(a+b) と足したら1を越えるのが何本あるか
// O(log |S|)
int bs(ll a, ll b, const vpii &S) {
  int ok = sz(S);
  int ng = -1;

  auto check = [&](int s) -> bool {
    ll c = S[s].A;
    ll d = S[s].B;
    return a*(c+d)+c*(a+b) > (a+b)*(c+d);
  };

  while (abs(ok - ng) > 1) {
    int mid = (ok + ng) / 2;
    bool c = check(mid);
    // cout << "ok: " << ok << ", ng: " << ng << ", ";
    // cout << "check(" << mid << ") -> " << c << endl;
    if (c) ok = mid;
    else ng = mid;
  }
  return sz(S) - ok;
}

void Main() {
  int n = read<int>();

  vpii R[3];

  rep(i, n) {
    int t = read<int>();
    int a = read<int>();
    int b = read<int>();
    int g = __gcd(a, b);
    a /= g;
    b /= g;

    R[t].emplace_back(a, b);
  }

  rep(i, 3) sort(all(R[i]), cmp_b);
  //rep(ii,3) { cout << "R["<<ii<<"]:"; rep(jj, sz(R[ii])) cout << ' ' << R[ii][jj]; cout << endl; }

  ll ans = 1 + n;

  forr(ab, R[1]) {
    int a = ab.A;
    int b = ab.B;
    int c0 = bs(a, b, R[0]);

    //_p("R1: a:%d, b:%d, c0: %d\n", a, b, c0);

    ans += c0;
  }

  forr(ab, R[2]) {
    ll a = ab.A;
    ll b = ab.B;
    int c0 = bs(a, b, R[0]);
    int c1 = bs(a, b, R[1]);

    //_p("R2: a:%lld, b:%lld, c0: %d, c1: %d\n", a, b, c0, c1);

    ans += c0;
    ans += c1;
  }

  vvi CC(4001, vi(4001));

  // R[0] と R[1] O(N^2)
  vd X;
  {
    forr(ab, R[0]) {
      ll a = ab.A;
      ll b = ab.B;
      forr(cd, R[1]) {
        ll c = cd.A;
        ll d = cd.B;
        if (a*(c+d) + c*(a+b) >= (a+b)*(c+d)) {
          if (cmp(a, a+b, c, c+d) <= 0) {
            X.emplace_back(1.0 * a / (a + b));
          }
          else {
            X.emplace_back(1.0 * c / (c + d));
          }
          {
            ll e = (a+b)*d + (c+d)*b;
            ll f = (a+b)*c - (c+d)*b;
            if (f > 0) {
              ll g = __gcd(e, f);
              e /= g;
              f /= g;
              if (e <= 4000 && f <= 4000) {
                CC[e][f]++;
                //_p("CC[%lld][%lld]++\n", e, f);
              }
            }
          }
        }
      }
    }
  }

  // O(N^2 log N^2) TLE?
  sort(all(X));
  //cout << "X:"; rep(ii,sz(X)) cout << ' ' << X[ii]; cout << endl;

  // 3本
  // O(n * log(N^2))
  forr(ab, R[2]) {
    ll a = ab.A;
    ll b = ab.B;
    double bab = 1.0 * b / (a + b);
    // b/(a+b) 以上の X を数える
    // X は単調増加
    // OK な下限を探すパターン
    int ok = sz(X);
    int ng = -1;

    auto check = [&](int x) -> bool {
      //_p("%d,%d,%lld,%lld\n",X[x].A, X[x].A + X[x].B, b, a + b);
      return X[x] >= bab;
      //return cmp(X[x].A, X[x].A + X[x].B, b, a + b) >= 0;
    };

    while (abs(ok - ng) > 1) {
      int mid = (ok + ng) / 2;
      bool c = check(mid);
      // cout << "ok: " << ok << ", ng: " << ng << ", ";
      // cout << "check(" << mid << ") -> " << c << endl;
      if (c) ok = mid;
      else ng = mid;
    }
    //cout << "ok: "<<ok << endl;
    ans += sz(X) - ok;

    // 交点に重なる場合を除く
    ans -= CC[a][b];
  }

  cout << ans << endl;

}
int main() { cin.tie(nullptr); ios::sync_with_stdio(false); Main(); return 0; }
0