Submission #1561045

---

Source Code Expand

// Copyright (C) 2017 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.

#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>
#include <cstdint>
#include <cinttypes>
#include <string.h>
#include <random>
#include <numeric>
#include <tuple>


using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

#define pb push_back
#define eb emplace_back

const int mod = 998244353;

int mult(int a, int b) {
    return int64_t(a) * b % mod;
}

int add(int a, int b) {
    return (a + b) % mod;
}

int sub(int a, int b) {
    return (mod + a - b) % mod;
}


int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    // code here.
    int n = input<int>();
    vector<pair<int, int>> crd(n);

    for (int i = 0; i != n; ++i)
        cin >> crd[i].first >> crd[i].second;

    vector<int> pws(n + 1);
    pws[0] = 1;
    for (int i = 1; i <= n; ++i)
        pws[i] = mult(pws[i - 1], 2);

    int ans = sub(pws[n], n + 1);

    vector<vector<char>> mat(n, vector<char>(n));

    auto line = [](pair<int, int> a, pair<int, int> b, pair<int, int> c) {
        pair<int, int> v = {b.first - a.first, b.second - a.second};
        pair<int, int> u = {c.first - a.first, c.second - a.second};

        return (v.first * int64_t(u.second) - v.second * int64_t(u.first) == 0);
    };
    
    for (int i = 0; i != n; ++i)
        for (int j = i + 1; j != n; ++j) {
            if (mat[i][j])
                continue;
            
            vector<int> lst;
            for (int k = 0; k != n; ++k)
                if (line(crd[i], crd[j], crd[k]))
                    lst.pb(k);

            for (int a: lst)
                for (int b: lst)
                    mat[a][b] = 1;

//            cerr << SZ(lst) << "\n";
            
            ans = sub(ans, sub(pws[SZ(lst)], SZ(lst) + 1));
        }

    cout << ans << "\n";
    
    return 0;
}

Submission Info

Judge Result