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

• 問題: No.1041 直線大学
• ユーザー: iiljj
• 提出日時: 2020-05-02 03:54:23
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 6 ms / 2,000 ms
• コード長: 16,536 bytes
• コンパイル時間: 2,661 ms
• コンパイル使用メモリ: 223,988 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-16 07:58:52
• 合計ジャッジ時間: 3,730 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 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	3 ms; 5,248 KB
testcase_13	AC	3 ms; 5,248 KB
testcase_14	AC	6 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	4 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	4 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	3 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

ソースコード

/* #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();
    RationalNum(double x);
    RationalNum(int numerator_, int denominator_ = 1);

    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_);
    int getNumerator() const;
    void setDenominator(int denominator_);
    int getDenominator() const;

  private:
    int numerator;
    int denominator;
    void simplify();
};

void getFactors(int num, vector<int> &factorSet) {
    if (num != 1) factorSet.push_back(num);
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) factorSet.push_back(i), factorSet.push_back(num / i);
    }
}

void simplifyFun(int &a, int &b) {
    int tempN = a, tempD = b;
    int small, temp;
    vector<int> factorSet;
    if (tempN == tempD) {
        a = 1, b = 1;
        return;
    } else if (tempN == -tempD) {
        a = -1, b = 1;
        return;
    } else if (tempN == 0) {
        b = 1;
        return;
    }

    small = min(abs(tempN), abs(tempD));

    getFactors(small, factorSet);
    for (int i = 0; i < factorSet.size(); i++) {
        temp = factorSet[i];
        while (tempN % temp == 0 && tempD % temp == 0) tempN /= temp, tempD /= temp;
    }
    if (b < 0) tempN *= -1, tempD *= -1;
    a = tempN, b = tempD;
}

/* #region RationalFriendFunctions */

RationalNum operator+(const RationalNum &left, const RationalNum &right) {
    RationalNum temp;
    int tempLD = left.getDenominator();
    int tempRD = right.getDenominator();
    simplifyFun(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) {
    RationalNum temp;
    RationalNum temp_2(right.getNumerator(), left.getDenominator());
    RationalNum temp_3(left.getNumerator(), right.getDenominator());
    int a = temp_2.getDenominator();
    int b = temp_2.getNumerator();
    int c = temp_3.getDenominator();
    int d = temp_3.getNumerator();
    temp.setNumerator(b * d);
    temp.setDenominator(a * c);
    return temp;
}

RationalNum operator/(const RationalNum &left, const RationalNum &right) {
    RationalNum temp_1(left.getNumerator(), left.getDenominator());
    RationalNum temp_2(right.getDenominator(), right.getNumerator());
    return temp_1 * temp_2;
}

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() { setNumerator(0), setDenominator(1); }

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(int numerator_, int denominator_) {
    setNumerator(numerator_);
    setDenominator(denominator_);
    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 {
    RationalNum temp;
    temp.setNumerator(-getNumerator());
    temp.setDenominator(getDenominator());
    return temp;
}

void RationalNum::setNumerator(int numerator_) { numerator = numerator_; }

int RationalNum::getNumerator() const { return numerator; }

void RationalNum::setDenominator(int denominator_) {
    if (denominator_ == 0) {
        denominator = 1, numerator = 0;
        cerr << "Denominator is 0! Not good! THe whole is set to 0." << endl;
    } else {
        denominator = denominator_;
    }
}

int RationalNum::getDenominator() const { return denominator; }

void RationalNum::simplify() {
    int tempN = numerator, tempD = denominator;
    simplifyFun(tempN, tempD);
    setNumerator(tempN);
    setDenominator(tempD);
}

/* #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;
}