제출 #1299558

#제출 시각아이디문제언어결과실행 시간메모리
1299558SamNguyenGeometrija (COCI21_geometrija)C++20
20 / 110
19 ms584 KiB
#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 double angle(const Vec2 &v1, const Vec2 &v2)
    {
        return acos(dot(v1.normalised(), v2.normalised()));
    }

    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);
    }
};

template <int N>
struct Triangulation
{
    int n;
    vector<int> adj[N];
    vector<pair<int, int>> segments;

    Triangulation() {}

    inline void add_edge(int i, int j)
    {
        adj[i].push_back(j);
        adj[j].push_back(i);
        segments.emplace_back(i, j);
    }

    void init(int _n, Vec2 pt[])
    {
        n = _n;
        add_edge(1, 2);
        add_edge(1, 3);
        add_edge(2, 3);

        for (int i = 4; i <= n; i++)
            for (int j = 1; j < i; j++)
            {
                bool is_crossing = false;
                Segment new_segment(pt[i], pt[j]);
                for (const auto &old_segment_idx : segments)
                {
                    int x, y;
                    tie(x, y) = old_segment_idx;
                    if (Segment::intersect_strict(new_segment, Segment(pt[x], pt[y])))
                    {
                        is_crossing = true;
                        break;
                    }
                }

                if (not is_crossing)
                    add_edge(j, i);
            }
    }
};

struct Cross
{
    vector<pair<double, double>> pt_angles_up;
    vector<pair<double, double>> pt_angles_down;

    Cross(int N, Vec2 pt[], int x, int y)
    {
        for (int p = 1; p <= N; p++)
            if (x != p and y != p)
            {
                Vec2 XP = pt[p] - pt[x];
                Vec2 YP = pt[p] - pt[y];
                Vec2 XY = pt[y] - pt[x];
                Vec2 YX = pt[x] - pt[y];

                double alpha = Vec2::angle(XP, XY);
                double beta = Vec2::angle(YP, YX);

                if (Vec2::cross(XY, XP) > 0)
                    pt_angles_up.emplace_back(alpha, beta);
                else
                    pt_angles_down.emplace_back(alpha, beta);
            }
    }

    inline bool is_crossed()
    {
        for (const auto &angles_up : pt_angles_up)
            for (const auto &angles_down : pt_angles_down)
            {
                double alpha_up, beta_up, alpha_down, beta_down;
                tie(alpha_up, beta_up) = angles_up;
                tie(alpha_down, beta_down) = angles_down;

                if (alpha_up + alpha_down < PI and beta_up + beta_down < PI)
                    return false;
            }

        return true;
    }
};

const int MAX = 1000 + 5;
int N;
Vec2 pt[MAX];
Triangulation<MAX> triangulation;

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);
    triangulation.init(N, pt);
}

void solve()
{
    int ans = 0;

    for (const auto &e : triangulation.segments)
    {
        int x, y;
        tie(x, y) = e;
        ans += Cross(N, pt, x, y).is_crossed() ? 1 : 0;
    }

    cout << ans;
}

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

    input();
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...