Submission #1299278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299278		SamNguyen	Geometrija (COCI21_geometrija)	C++20	20 / 110	1036 ms	576 KiB

geometrija

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);

template <class T1, class T2>
inline bool minimise(T1 &x, T2 y)
{
    if (x > y)
    {
        x = y;
        return true;
    }
    return false;
}

template <class T1, class T2>
inline bool maximise(T1 &x, T2 y)
{
    if (x < y)
    {
        x = y;
        return true;
    }
    return false;
}

template <class T>
inline constexpr int sgn(T x)
{
    if (x > 0)
        return 1;
    if (x < 0)
        return -1;
    return 0;
}

struct Vec2
{
    double x, y;

    Vec2(double x = 0, double y = 0) : x(x), y(y) {}

    inline Vec2 operator+(const Vec2 &oth) const { return Vec2(x + oth.x, y + oth.y); }
    inline Vec2 operator-(const Vec2 &oth) const { return Vec2(x - oth.x, y - oth.y); }
    inline double norm() const { return sqrt(x * x + y * y); }
    inline double norm_sq() const { return x * x + y * y; }
    inline Vec2 normalised() const
    {
        double l = norm();
        return Vec2(x / l, y / l);
    }

    inline static double dot(const Vec2 &v1, const Vec2 &v2)
    {
        return v1.x * v2.x + v1.y * v2.y;
    }

    inline static double cross(const Vec2 &v1, const Vec2 &v2)
    {
        return v1.x * v2.y - v1.y * v2.x;
    }

    inline static bool is_ccw(const Vec2 &origin, const Vec2 &p1, const Vec2 &p2)
    {
        Vec2 r1 = p1 - origin;
        Vec2 r2 = p2 - origin;
        return cross(r1, r2) > 0.;
    }

    inline static bool is_ray_order(const Vec2 &ray_1, const Vec2 &ray_mid, const Vec2 &ray_2, bool strict = false)
    {
        int _sgn = sgn(cross(ray_mid, ray_1)) * sgn(cross(ray_mid, ray_2));
        if (strict)
            return _sgn < 0;
        return _sgn <= 0;
    }

    // inline tuple<const int &, const int &> coords() const
    // {
    //     return tie(x, y);
    // }

    inline static bool compare_x(const Vec2 &v1, const Vec2 &v2)
    {
        if (v1.x != v2.x)
            return v1.x < v2.x;
        return v1.y < v2.y;
    }
};

struct Segment
{
    Vec2 pt[2];

    Segment(Vec2 A, Vec2 B)
    {
        pt[0] = A, pt[1] = B;
    }

    inline static bool intersect(Segment p, Segment q, bool strict = false)
    {
        Vec2 p1 = p.pt[0], p2 = p.pt[1];
        Vec2 q1 = q.pt[0], q2 = q.pt[1];

        return Vec2::is_ray_order(q1 - p1, p2 - p1, q2 - p1, strict) and
               Vec2::is_ray_order(p1 - q1, q2 - q1, p2 - q1, strict);
    }

    inline static bool intersect_strict(Segment p, Segment q)
    {
        return intersect(p, q, true);
    }
};

// struct Triangulation
// {
//     vector<int> adj[MAX];
// };

const int MAX = 1000 + 5;
int N;
Vec2 pt[MAX];

void input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        int x, y;
        cin >> x >> y;
        pt[i] = Vec2(x, y);
    }

    sort(pt + 1, pt + N + 1, Vec2::compare_x);
}

void solve()
{
    int ans = 0;
    for (int a = 1; a <= N; a++)
        for (int b = a + 1; b <= N; b++)
        {
            bool is_non_crossing = true;
            for (int c = 1; c <= N; c++)
                for (int d = c + 1; d <= N; d++)
                    if (Segment::intersect_strict(Segment(pt[a], pt[b]), Segment(pt[c], pt[d])))
                        is_non_crossing = false;

            if (is_non_crossing)
                ans++;
        }

    cout << ans;
}

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

    input();
    solve();

    return 0;
}

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