Submission #518247

#	Time	Username	Problem	Language	Result	Execution time	Memory
518247		Vimmer	Geometrija (COCI21_geometrija)	C++14	50 / 110	1085 ms	19732 KiB

geometrija

#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")

#define F first
#define S second
#define PB push_back
#define M ll(1e9 + 7)
#define sz(x) int(x.size())
#define N 1001
#define pri(x) cout << x << endl
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

using namespace std;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;

const ld eps = 1e-10;

pair <ld, ld> convert(int x1, int y1, int x2, int y2)
{
    ld k = 0;

    if (x2 != x1)
        k = ld(y2 - y1) / ld(x2 - x1);

    ld b = ld(y1) - k * x1;

    return {k, b};
}

pair <ld, ld> inter(pair <ld, ld> x, pair <ld, ld> y)
{
    if (fabs(x.F - y.F) < eps)
        return {1e18, 1e18};

    ld X = (y.S - x.S) / (x.F - y.F);

    ld Y = (x.F * X + x.S);

    return {X, Y};
}

pair <ld, ld> otr[N][N];

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

//    freopen("1.in", "r", stdin);

    int n;

    cin >> n;

    int x[n], y[n];

    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i];

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            otr[i][j] = convert(x[i], y[i], x[j], y[j]);

    int ans = 0;

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
        {
            bool gd = 0;

            for (int u = 0; u < n && !gd; u++)
            {
                if (i == u || j == u)
                    continue;

                for (int t = u + 1; t < n && !gd; t++)
                {
                    if (t == i || t == j)
                        continue;

                    if (x[i] == x[j])
                    {
                        if (x[u] == x[t])
                        {
                            continue;
                        }
                        else if (y[u] == y[t])
                        {
                            if (min(x[u], x[t]) <= x[i] && x[i] <= max(x[u], x[t]) && min(y[i], y[j]) <= y[u] && y[u] <= max(y[i], y[j]))
                            {
                                gd = 1;
                            }

                            continue;
                        }
                        else
                        {
                            if (min(x[u], x[t]) <= x[i] && x[i] <= max(x[u], x[t]))
                            {
                                ld yy = otr[u][t].F * x[i] + otr[u][t].S;

                                if (min(y[i], y[j]) - yy < eps && yy - max(y[i], y[j]) < eps)
                                {
                                    gd = 1;
                                }
                            }

                            continue;
                        }
                    }

                    if (y[i] == y[j])
                    {
                        if (y[u] == y[t])
                        {
                            continue;
                        }
                        else if (x[u] == x[t])
                        {
                            if (min(x[i], x[j]) <= x[u] && x[u] <= max(x[i], x[j]) && min(y[u], y[t]) <= y[i] && y[i] <= max(y[u], y[t]))
                            {
                                gd = 1;
                            }

                            continue;
                        }
                        else
                        {
                            if (min(y[u], y[t]) <= y[i] && y[i] <= max(y[u], y[t]))
                            {
                                ld xx = (y[i] - otr[u][t].S) / otr[u][t].F;

                                if (min(x[i], x[j]) - xx < eps && xx - max(x[i], x[j]) < eps)
                                {
                                    gd = 1;
                                }
                            }

                            continue;
                        }
                    }

                    if (x[u] == x[t])
                    {
                        if (min(x[i], x[j]) <= x[u] && x[u] <= max(x[i], x[j]))
                        {
                            ld yy = otr[i][j].F * x[u] + otr[i][j].S;

                            if (min(y[u], y[t]) - yy < eps && yy - max(y[u], y[t]) < eps)
                            {
                                gd = 1;
                            }
                        }

                        continue;
                    }

                    if (y[u] == y[t])
                    {
                        if (min(y[i], y[j]) <= y[u] && y[u] <= max(y[i], y[j]))
                        {
                            ld xx = (y[u] - otr[i][j].S) / otr[i][j].F;

                            if (min(x[u], x[t]) - xx < eps && xx - max(x[u], x[t]) < eps)
                            {
                                gd = 1;
                            }
                        }

                        continue;
                    }

                    pair <ld, ld> cur = inter(otr[i][j], otr[u][t]);

                    ld lx = min(x[i], x[j]);

                    ld rx = max(x[i], x[j]);

                    ld ly = min(y[i], y[j]);

                    ld ry = max(y[i], y[j]);

                    if (lx - cur.F < eps && cur.F - rx < eps)
                    {
                        if (ly - cur.S < eps && cur.S - ry < eps)
                        {
                            ld lx = min(x[u], x[t]);

                            ld rx = max(x[u], x[t]);

                            ld ly = min(y[u], y[t]);

                            ld ry = max(y[u], y[t]);

                            if (lx - cur.F < eps && cur.F - rx < eps)
                            {
                                if (ly - cur.S < eps && cur.S - ry < eps)
                                {
                                    gd = 1;
                                }
                            }
                        }
                    }
                }
            }

            if (!gd)
                ans++;
        }

    pri(ans);
}

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