結果

問題 No.461 三角形はいくつ？
ユーザー kuwa
提出日時 2016-12-12 01:30:23
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 WA * 26 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

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