#475409 (C++17) No.1041 直線大学

提出ソース

結果

問題	No.1041 直線大学
ユーザー	iiljj
提出日時	2020-05-02 14:48:13
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	6 ms / 2,000 ms
コード長	15,126 bytes
コンパイル時間	2,689 ms
コンパイル使用メモリ	221,992 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-16 07:59:55
合計ジャッジ時間	3,852 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 5,248 KB
testcase_01	AC	3 ms 5,248 KB
testcase_02	AC	3 ms 5,248 KB
testcase_03	AC	3 ms 5,248 KB
testcase_04	AC	3 ms 5,248 KB
testcase_05	AC	3 ms 5,248 KB
testcase_06	AC	3 ms 5,248 KB
testcase_07	AC	3 ms 5,248 KB
testcase_08	AC	4 ms 5,248 KB
testcase_09	AC	4 ms 5,248 KB
testcase_10	AC	4 ms 5,248 KB
testcase_11	AC	3 ms 5,248 KB
testcase_12	AC	4 ms 5,248 KB
testcase_13	AC	4 ms 5,248 KB
testcase_14	AC	5 ms 5,248 KB
testcase_15	AC	4 ms 5,248 KB
testcase_16	AC	5 ms 5,248 KB
testcase_17	AC	3 ms 5,248 KB
testcase_18	AC	5 ms 5,248 KB
testcase_19	AC	5 ms 5,248 KB
testcase_20	AC	3 ms 5,248 KB
testcase_21	AC	4 ms 5,248 KB
testcase_22	AC	3 ms 5,248 KB
testcase_23	AC	6 ms 5,248 KB
testcase_24	AC	5 ms 5,248 KB
testcase_25	AC	4 ms 5,248 KB
testcase_26	AC	3 ms 5,248 KB
testcase_27	AC	3 ms 5,248 KB
testcase_28	AC	3 ms 5,248 KB
testcase_29	AC	3 ms 5,248 KB
testcase_30	AC	3 ms 5,248 KB
testcase_31	AC	3 ms 5,248 KB
testcase_32	AC	3 ms 5,248 KB
testcase_33	AC	3 ms 5,248 KB
testcase_34	AC	3 ms 5,248 KB
testcase_35	AC	3 ms 5,248 KB
testcase_36	AC	4 ms 5,248 KB
testcase_37	AC	3 ms 5,248 KB
testcase_38	AC	6 ms 5,248 KB
testcase_39	AC	3 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

/* #region Head */

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using vll = vc<ll>;
using vvll = vvc<ll>;
using vld = vc<ld>;
using vvld = vvc<ld>;
using vs = vc<string>;
using vvs = vvc<string>;
template <class T, class U> using um = unordered_map<T, U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqa = priority_queue<T, vc<T>, greater<T>>;
template <class T> using us = unordered_set<T>;

#define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i))
#define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i))
#define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i))
#define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d))
#define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d))
#define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define ALL(x) begin(x), end(x)
#define SIZE(x) ((ll)(x).size())
#define PERM(c)                                                                                                        \
    sort(ALL(c));                                                                                                      \
    for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))
#define UNIQ(v) v.erase(unique(ALL(v)), v.end());

#define endl '\n'
#define sqrt sqrtl
#define floor floorl
#define log2 log2l

constexpr ll INF = 1'010'000'000'000'000'017LL;
constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.14159265358979323846;

template <typename T> istream &operator>>(istream &is, vc<T> &vec) { // vector 入力
    for (T &x : vec) is >> x;
    return is;
}
template <typename T> ostream &operator<<(ostream &os, vc<T> &vec) { // vector 出力 (for dump)
    os << "{";
    REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T> ostream &operator>>(ostream &os, vc<T> &vec) { // vector 出力 (inline)
    REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " ");
    return os;
}

template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &pair_var) { // pair 入力
    is >> pair_var.first >> pair_var.second;
    return is;
}
template <typename T, typename U> ostream &operator<<(ostream &os, pair<T, U> &pair_var) { // pair 出力
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}

// map, um, set, us 出力
template <class T> ostream &out_iter(ostream &os, T &map_var) {
    os << "{";
    REPI(itr, map_var) {
        os << *itr;
        auto itrcp = itr;
        if (++itrcp != map_var.end()) os << ", ";
    }
    return os << "}";
}
template <typename T, typename U> ostream &operator<<(ostream &os, map<T, U> &map_var) { return out_iter(os, map_var); }
template <typename T, typename U> ostream &operator<<(ostream &os, um<T, U> &map_var) { return out_iter(os, map_var); }
template <typename T> ostream &operator<<(ostream &os, set<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, us<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, pq<T> &pq_var) {
    pq<T> pq_cp(pq_var);
    os << "{";
    if (!pq_cp.empty()) {
        os << pq_cp.top(), pq_cp.pop();
        while (!pq_cp.empty()) os << ", " << pq_cp.top(), pq_cp.pop();
    }
    return os << "}";
}

// dump
#define DUMPOUT cerr
void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head &&head, Tail &&... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) DUMPOUT << ", ";
    dump_func(move(tail)...);
}

// chmax (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmax(T &xmax, const U &x, Comp comp = {}) {
    if (comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

// chmin (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmin(T &xmin, const U &x, Comp comp = {}) {
    if (comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

// ローカル用
#define DEBUG_

#ifdef DEBUG_
#define DEB
#define dump(...)                                                                                                      \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                                                                    \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl                                        \
            << "    ",                                                                                                 \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif

struct AtCoderInitialize {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
    AtCoderInitialize() {
        ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
        cout << fixed << setprecision(IOS_PREC);
        if (AUTOFLUSH) cout << unitbuf;
    }
} ATCODER_INITIALIZE;

string yes = "Yes", no = "No";
// string yes = "YES", no = "NO";
void yn(bool p) { cout << (p ? yes : no) << endl; }

/* #endregion */

/* #region Rational */

class RationalNum {
    friend RationalNum operator+(const RationalNum &left, const RationalNum &right);
    friend RationalNum operator-(const RationalNum &left, const RationalNum &right);
    friend RationalNum operator*(const RationalNum &left, const RationalNum &right);
    friend RationalNum operator/(const RationalNum &left, const RationalNum &right);
    friend bool operator==(const RationalNum &left, const RationalNum &right);
    friend bool operator!=(const RationalNum &left, const RationalNum &right);
    friend bool operator<(const RationalNum &left, const RationalNum &right);
    friend bool operator>(const RationalNum &left, const RationalNum &right);
    friend bool operator<=(const RationalNum &left, const RationalNum &right);
    friend bool operator>=(const RationalNum &left, const RationalNum &right);
    friend ostream &operator<<(ostream &out, const RationalNum &obj);
    friend istream &operator>>(istream &in, RationalNum &obj);

  public:
    RationalNum() { numerator = 0, denominator = 1; }
    RationalNum(double x);
    RationalNum(int numerator_, int denominator_ = 1) {
        numerator = numerator_, denominator = denominator_;
        simplify();
    }

    RationalNum &operator=(const RationalNum &obj);
    RationalNum &operator+=(const RationalNum &obj);
    RationalNum &operator-=(const RationalNum &obj);
    RationalNum &operator*=(const RationalNum &obj);
    RationalNum &operator/=(const RationalNum &obj);
    RationalNum &operator++();
    RationalNum operator++(int);
    RationalNum &operator--();
    RationalNum operator--(int);
    RationalNum operator+() const;
    RationalNum operator-() const;

    void setNumerator(int numerator_) { numerator = numerator_; }
    int getNumerator() const { return numerator; }
    void setDenominator(int denominator_) { denominator = denominator_, (assert(denominator != 0)); }
    int getDenominator() const { return denominator; }

    static void simplifyNums(int &numerator_, int &denominator_) {
        if (denominator_ == 0) numerator_ = abs(numerator_);
        int g = __gcd(numerator_, denominator_);
        numerator_ /= g, denominator_ /= g;
        if (denominator_ < 0) numerator_ *= -1, denominator_ *= -1;
    }

    RationalNum inv() const { return RationalNum(denominator, numerator); }

  private:
    int numerator;
    int denominator;
    void simplify() { RationalNum::simplifyNums(numerator, denominator); }
};

/* #region RationalFriendFunctions */

RationalNum operator+(const RationalNum &left, const RationalNum &right) {
    RationalNum temp;
    int tempLD = left.getDenominator();
    int tempRD = right.getDenominator();
    RationalNum::simplifyNums(tempLD, tempRD);
    temp.setDenominator(left.getDenominator() * tempRD);
    temp.setNumerator(left.getNumerator() * tempRD + right.getNumerator() * tempLD);
    temp.simplify();
    return temp;
}

RationalNum operator-(const RationalNum &left, const RationalNum &right) { return left + (-right); }

RationalNum operator*(const RationalNum &left, const RationalNum &right) {
    int a = left.denominator, b = right.numerator, c = right.denominator, d = left.numerator;
    RationalNum::simplifyNums(b, a), RationalNum::simplifyNums(d, c);
    return RationalNum(b * d, a * c);
}

RationalNum operator/(const RationalNum &left, const RationalNum &right) { return left * right.inv(); }

bool operator==(const RationalNum &left, const RationalNum &right) {
    return (left.numerator == right.numerator && left.denominator == right.denominator);
}

bool operator!=(const RationalNum &left, const RationalNum &right) { return !(left == right); }

bool operator<(const RationalNum &left, const RationalNum &right) {
    int lside = left.getNumerator() * right.getDenominator();
    int rside = left.getDenominator() * right.getNumerator();
    return (lside < rside);
}

bool operator>(const RationalNum &left, const RationalNum &right) {
    int lside = left.getNumerator() * right.getDenominator();
    int rside = left.getDenominator() * right.getNumerator();
    return (lside > rside);
}

bool operator<=(const RationalNum &left, const RationalNum &right) { return ((left < right) || (left == right)); }

bool operator>=(const RationalNum &left, const RationalNum &right) { return ((left > right) || (left == right)); }

// 出力
ostream &operator<<(ostream &out, const RationalNum &obj) {
    out << obj.numerator;
    if (obj.numerator != 0 && obj.denominator != 1) out << "/" << obj.denominator;
    return out;
}

// 入力
istream &operator>>(istream &in, RationalNum &obj) {
    string inputstr;
    int num = 0;
    int sign = 1;
    bool slashExist = false;
    bool dotExist = false;
    bool validInput = true;
    int virtualDenominator = 1;
    cin >> inputstr;
    for (int i = 0; i < inputstr.size(); i++) {
        char temp = inputstr[i];
        if (temp == '.') {
            if (dotExist == false && slashExist == false && i != 0) {
                dotExist = true;
            } else {
                validInput = false;
                break;
            }
        } else if (temp == '/') {
            if (dotExist == false && slashExist == false && i != 0) {
                slashExist = true;
                obj.setNumerator(sign * num);
                num = 0;
                sign = 1;
            } else {
                validInput = false;
                break;
            }
        } else if (temp == '-') {
            if (i == 0) {
                sign = -sign;
            } else if (inputstr[i - 1] == '/') {
                sign = -sign;
            } else {
                validInput = false;
                break;
            }
        } else if (temp <= '9' && temp >= '0') {
            if (dotExist) {
                if (virtualDenominator > INT_MAX / 10) {
                    cout << "this frational is too long to handle.";
                    validInput = false;
                    break;
                } else {
                    virtualDenominator *= 10;
                }
            }
            if (num > INT_MAX / 10) {
                cout << "this number is too long to handle.";
                validInput = false;
                break;
            }
            num *= 10;
            num += inputstr[i] - '0';
        } else {
            validInput = false;
            break;
        }
    }

    if (validInput == false) {
        obj.setNumerator(0);
        obj.setDenominator(1);
        cout << "Input is not valid! The whole set to 0" << endl;
    } else {
        if (slashExist == true) {
            obj.setDenominator(sign * num);
        } else if (dotExist) {
            obj.setNumerator(sign * num);
            obj.setDenominator(virtualDenominator);
        } else {
            obj.setNumerator(sign * num);
            obj.setDenominator(1);
        }
    }
    obj.simplify();
    return in;
}

/* #endregion */

/* #region RationalMemberFunctions */

RationalNum::RationalNum(double x) {
    int i = 1;
    while (x * i - static_cast<int>(x * i) != 0) {
        if (i > INT_MAX / 10) {
            cout << "this frational number : " << x
                 << " can not be transfer to rational number, it's too long, now set it 0." << endl;
            setNumerator(0), setDenominator(1);
            return;
        } else {
            i *= 10;
        }
    }
    setNumerator(x * i);
    setDenominator(i);
    simplify();
}

RationalNum &RationalNum::operator=(const RationalNum &obj) {
    setNumerator(obj.getNumerator()), setDenominator(obj.getDenominator());
    return *this;
}

RationalNum &RationalNum::operator+=(const RationalNum &obj) { return *this = *this + obj; }
RationalNum &RationalNum::operator-=(const RationalNum &obj) { return *this = *this - obj; }
RationalNum &RationalNum::operator*=(const RationalNum &obj) { return *this = *this * obj; }
RationalNum &RationalNum::operator/=(const RationalNum &obj) { return *this = *this / obj; }
RationalNum &RationalNum::operator++() { return *this = *this + 1; }

RationalNum RationalNum::operator++(int) {
    RationalNum before = *this;
    *this = *this + 1;
    return before;
}

RationalNum &RationalNum::operator--() { return *this = *this - 1; }

RationalNum RationalNum::operator--(int) {
    RationalNum before = *this;
    *this = *this - 1;
    return before;
}

RationalNum RationalNum::operator+() const { return *this; }

RationalNum RationalNum::operator-() const { return RationalNum(-numerator, denominator); }

/* #endregion */
/* #endregion */

// Problem
void solve() {
    int n;
    cin >> n;
    vc<int> x(n), y(n);
    REP(i, 0, n) cin >> x[i] >> y[i];
    vc<int> vertical(101, 0);
    map<pair<RationalNum, RationalNum>, int> lines;
    REP(i, 0, n - 1) REP(j, i + 1, n) {
        if (x[i] == x[j]) {
            ++vertical[x[i]];
        } else {
            RationalNum a = y[j] - y[i];
            a /= x[j] - x[i];
            RationalNum b = -a * x[i] + y[i];
            pair<RationalNum, RationalNum> key = make_pair(a, b);
            lines[key];
            ++lines[key];
            // if ((i == 0 || i == 1) && (j == 1 || j == 3)) dump(i, j, a, b);
        }
    }

    um<int, int> linenum2pointnum;
    linenum2pointnum[0] = 0;
    REPM(i, 2, 10000) linenum2pointnum[i * (i - 1) / 2] = i;
    int ma = linenum2pointnum[*max_element(ALL(vertical))];
    // dump(vertical, ma);
    REPI(itr, lines) chmax(ma, linenum2pointnum[itr->second]);
    //, (dump(itr->first.first, itr->first.second, itr->second));
    cout << ma << endl;
    // dump(lines);
}

// entry point
int main() {
    solve();
    return 0;
}

yukicoder

結果

テストケース

ソースコード