#137815 (C++14) No.461 三角形はいくつ？

• 問題: No.461 三角形はいくつ？
• ユーザー: しらっ亭
• 提出日時: 2016-12-12 03:15:18
• 言語: C++14 (gcc 13.3.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 4,426 bytes
• コンパイル時間: 1,711 ms
• コンパイル使用メモリ: 185,204 KB
• 実行使用メモリ: 226,268 KB
• 最終ジャッジ日時: 2024-11-29 13:53:33
• 合計ジャッジ時間: 68,765 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 4
other	AC * 7 WA * 3 RE * 25 TLE * 6

ソースコード

#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

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;
}

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

void Main() {
  int n = read<int>();
  vector<pair<int, pii>> L;

  vvpii 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,sz(R)) { cout << "R["<<ii<<"]:"; rep(jj, sz(R[ii])) cout << ' ' << R[ii][jj]; cout << endl; }

  ll ans = 1 + n;

  auto bs = [&](ll a, ll b, const vpii &S) -> int {
    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;
  };

  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;
  }

  // R[0] と R[1] O(N^2)
  vpii X;
  unordered_map<ll, int> CC;
  {
    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(a, b);
          }
          else {
            X.emplace_back(c, d);
          }
          {
            ll e = (a+b)*d + (c+d)*b;
            ll f = (a+b)*c - (c+d)*b;
            if (e != 0 && f != 0) {
              ll g = __gcd(e, f);
              e /= g;
              f /= g;
              CC[(e << 32) + f]++;
              //_p("CC[%lld,%lld]++\n", e, f);
            }
          }
        }
      }
    }
  }
  sort(all(X), cmp_b);
  //cout << "X:"; rep(ii,sz(X)) cout << ' ' << X[ii]; cout << endl;

  // 3本
  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;

    // 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 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<<32)+b];
      }
    }
  }

  cout << ans << endl;

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