結果

問題 No.461 三角形はいくつ？
ユーザー kuwakuwa
提出日時 2016-12-12 01:30:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,427 bytes
コンパイル時間 1,295 ms
コンパイル使用メモリ 95,504 KB
実行使用メモリ 265,184 KB
最終ジャッジ日時 2024-11-29 05:51:03
合計ジャッジ時間 98,369 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
145,040 KB
testcase_01 AC 2 ms
10,496 KB
testcase_02 AC 2 ms
150,024 KB
testcase_03 AC 2 ms
143,852 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 9 ms
5,248 KB
testcase_17 AC 9 ms
5,248 KB
testcase_18 TLE -
testcase_19 TLE -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 AC 7 ms
5,248 KB
testcase_28 AC 6 ms
5,248 KB
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 AC 6 ms
5,248 KB
testcase_34 AC 6 ms
5,248 KB
testcase_35 AC 6 ms
5,248 KB
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdint>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

using int64 = int64_t;

int64 gcd(int64 x, int64 y) {
    if (y == 0) { return x; }
    return gcd(y, x%y);
}

struct line {
    int p;
    int64 a, b;
    line() {}

    bool operator < (const line& o) const { return p < o.p; }
};

struct rat {
    int64 nume, deno;
    rat(){}
    rat(int64 a, int64 b): nume(a), deno(b) {
        int64 t = gcd(nume, deno);
        nume /= t; deno /= t;
    }

    bool operator < (const rat& o) const { return nume * o.deno < deno * o.nume; }
};

int N;
line l[4040];

int main() {
    cin >> N;
    for (int j = 0; j < N; ++j) {
        cin >> l[j].p >> l[j].a >> l[j].b;
    }

    sort(l, l+N);

    vector<rat> ts;

    map<rat, int64> tmp;
    map<rat, int64> crs;

    int ind0, ind1;
    for (ind0 = 0; ind0 < N && l[ind0].p == 0; ++ind0) {
        ts.emplace_back(l[ind0].b, l[ind0].a + l[ind0].b);
    }
    for (ind1 = ind0; ind1 < N && l[ind1].p == 1; ++ind1) {
        ts.emplace_back(l[ind1].b, l[ind1].a + l[ind1].b);
    }

    int64 count = 1 + ind1;

    ts.emplace_back(0, 1);
    for (int j = 0; j < ind0; ++j) { for (int k = ind0; k < ind1; ++k) {
        int64 nume = l[j].a * (l[k].a + l[k].b) + l[k].a * (l[j].a + l[j].b);
        int64 deno = (l[j].a + l[j].b) * (l[k].a + l[k].b);
        if (nume < deno) { continue; }

        int64 x = nume - deno;
        int64 y = 2 * deno - nume;
        rat hi = rat(y, x+y);
        if (nume > deno) {
            ++count;
            ts.emplace_back(y, x+y);
        }

        rat r0(l[j].b, l[j].a+l[j].b);
        rat r1(l[k].b, l[k].a+l[k].b);
        rat lo = r0 < r1 ? r1 : r0;
        if (tmp.find(lo) == end(tmp)) {
            tmp[lo] = 1;
        } else { ++tmp[lo]; }
        if (tmp.find(hi) == end(tmp)) {
            tmp[hi] = -1;
        } else { --tmp[hi]; }
    } }
    sort(begin(ts), end(ts));

    int64 acc = 0;
    for (pair<rat, int64> p : tmp) {
        acc += p.second;
        crs[p.first] = acc;
    }
    crs[rat(2, 1)] = acc;


    for (int j = ind1; j < N; ++j) {
        auto val = rat(l[j].a, l[j].b+l[j].a);
        {
            auto it = lower_bound(begin(ts), end(ts), val);
            count += it - begin(ts);
        }
        {
            auto it = crs.lower_bound(val);
            count += it->second;
        }
    }

    cout << count << endl;

    return 0;
}
0