Submission #386347

#	Time	Username	Problem	Language	Result	Execution time	Memory
386347		model_code	Geometrija (COCI21_geometrija)	C++17	50 / 110	1092 ms	492 KiB

geometrija

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

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

int sign(ll x) {
    if (x > 0) return 1;
    if (x < 0) return -1;
    return 0;
}

int ccw(const pii& a, const pii& b, const pii& c) {
    return sign((ll)a.fi * (b.se - c.se) +
                (ll)b.fi * (c.se - a.se) +
                (ll)c.fi * (a.se - b.se));
}


bool intersect(const pii& a, const pii& b, const pii& c, const pii& d) {
    if (a == b || a == c || a == d || b == c || b == d || c == d) return false;
    return ccw(a, b, c) != ccw(a, b, d) && ccw(c, d, a) != ccw(c, d, b);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    vector<pii> pts(n);
    for (auto& it : pts) cin >> it.fi >> it.se;

    int sol = 0;
    vector<pair<pii, pii>> tr;
    for (auto& a : pts) for (auto& b : pts) {
        if (a == b) continue;

        bool ok = true;
        for (auto& it : tr)
            ok &= !intersect(a, b, it.fi, it.se) && (it != make_pair(b, a));

        if (!ok) continue;

        tr.push_back({a, b});

        for (auto& c : pts) for (auto& d : pts)
            ok &= !intersect(a, b, c, d);
        sol += ok;
    }

    cout << sol << '\n';

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60