結果
問題 | No.461 三角形はいくつ? |
ユーザー |
|
提出日時 | 2017-07-09 17:42:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,004 ms / 5,000 ms |
コード長 | 3,912 bytes |
コンパイル時間 | 1,123 ms |
コンパイル使用メモリ | 111,680 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-07 04:41:02 |
合計ジャッジ時間 | 33,919 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#define _USE_MATH_DEFINES#include <cstdio>#include <iostream>#include <sstream>#include <fstream>#include <iomanip>#include <algorithm>#include <cmath>#include <complex>#include <string>#include <vector>#include <list>#include <queue>#include <stack>#include <set>#include <map>#include <bitset>#include <numeric>#include <limits>#include <climits>#include <cfloat>#include <functional>#include <iterator>using namespace std;template <class T1>class Operators{public:template <class T2>const T1 operator+(const T2& right) const{T1 ans = static_cast<const T1&>( *this );ans += right;return ans;}template <class T2>const T1 operator-(const T2& right) const{T1 ans = static_cast<const T1&>( *this );ans -= right;return ans;}template <class T2>const T1 operator*(const T2& right) const{T1 ans = static_cast<const T1&>( *this );ans *= right;return ans;}template <class T2>const T1 operator/(const T2& right) const{T1 ans = static_cast<const T1&>( *this );ans /= right;return ans;}bool operator!=(const T1& right) const{const T1& left = static_cast<const T1&>( *this );return !(left == right);}bool operator>(const T1& right) const{const T1& left = static_cast<const T1&>( *this );return right < left;}bool operator<=(const T1& right) const{const T1& left = static_cast<const T1&>( *this );return !(right < left);}bool operator>=(const T1& right) const{const T1& left = static_cast<const T1&>( *this );return !(left < right);}};class Fraction : public Operators<Fraction>{private:long long n; // 分子(numerator)long long d; // 分母(denominator)// 約分void reduce(){if(d < 0){n *= -1;d *= -1;}long long a = abs(n);long long b = d;while(b != 0){long long tmp = a % b;a = b;b = tmp;}n /= a;d /= a;}public:Fraction(){n = 0;d = 1;}Fraction(long long n0){n = n0;d = 1;}Fraction(long long n0, long long d0){n = n0;d = d0;reduce();}pair<long long, long long> getValue() const{return make_pair(n, d);}Fraction& operator+=(const Fraction& f){n = n * f.d + d * f.n;d *= f.d;reduce();return *this;}Fraction& operator-=(const Fraction& f){n = n * f.d - d * f.n;d *= f.d;reduce();return *this;}Fraction& operator*=(const Fraction& f){n *= f.n;d *= f.d;reduce();return *this;}Fraction& operator/=(const Fraction& f){n *= f.d;d *= f.n;reduce();return *this;}bool operator==(const Fraction& f) const{return n == f.n && d == f.d;}bool operator<(const Fraction& f) const{return n * f.d < f.n * d;}};int main(){int n;cin >> n;vector<vector<Fraction> > v(3, vector<Fraction>(1, 1));for(int i=0; i<n; ++i){int p, a, b;cin >> p >> a >> b;v[p].push_back(Fraction(a, a + b));}long long ans = 0;sort(v[0].begin(), v[0].end());for(Fraction a : v[1]){for(Fraction b : v[2]){if(a + b < 1)continue;Fraction c = Fraction(1) - min(a, b);ans += v[0].end() - lower_bound(v[0].begin(), v[0].end(), c);Fraction d = Fraction(2) - a - b;if(binary_search(v[0].begin(), v[0].end(), d))-- ans;}}cout << ans << endl;return 0;}