Submission #1167950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167950		sunflower	Geometrija (COCI21_geometrija)	C++17	20 / 110	1095 ms	3756 KiB

geometrija

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

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl

#define left    __left
#define right   __right
#define prev    __prev
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int n;

#define MAX_POINT 1'010

struct Point {
    ll x, y;

    Point(ll _x = 0, ll _y = 0) {
        x = _x, y = _y;
    }
    void input() {
        cin >> x >> y;
    }

    Point operator - (const Point &other) const {
        return Point(x - other.x, y - other.y);
    }
} p[MAX_POINT + 2];

using Vecto = Point;

ll dot(Vecto A, Vecto B) {
    return A.x * B.x + A.y * B.y;
}

ll cross(Vecto A, Vecto B) {
    return A.x * B.y - A.y * B.x;
}

ll cross(Point A, Point B, Point C) {
    Vecto AB = B - A, AC = C - A;
    return cross(AB, AC);
}

int sign(ll x) {
    return (x > 0 ? 1 : (x == 0 ? 0 : -1));
}

struct Line {
    Point a, b;
};

// AB . AC = |AB| * |AC| * cos(AB, AC)

bool inside(Point A, Point B, Point C) { // C in segment AB;
    Vecto CA = A - C, CB = B - C;
    return (dot(CA, CB) <= 0 && cross(CA, CB) == 0);

    // dot(CA, CB) == 0 khi C trungf A or C trungf B;
    // dot(CA, CB) < 0 ==> dot(CA, CB) == 1 ==> C nam giua A va B;
}

bool intersect(Line X, Line Y) {
    if (inside(X.a, X.b, Y.a)) return false;
    if (inside(X.a, X.b, Y.b)) return false;

    if (inside(Y.a, Y.b, X.a)) return false;
    if (inside(Y.a, Y.b, X.b)) return false;

    int direct_one = sign(cross(X.a, X.b, Y.a));
    int direct_two = sign(cross(X.a, X.b, Y.b));

    int direct_three = sign(cross(Y.a, Y.b, X.a));
    int direct_four = sign(cross(Y.a, Y.b, X.b));

    return (direct_one * direct_two < 0 && direct_three * direct_four < 0);
}

namespace subtask1 {
    bool check() {
        return (n <= 40);
    }

    Line arr[100000];
    bool ok[100000];

    void solve() {
        int cur = 0;
        FOR(i, 1, n) {
            FOR(j, i + 1, n) {
                arr[++cur] = {p[i], p[j]};
            }
        }

        memset(ok, true, sizeof(ok));
        FOR(i, 1, cur) {
            FOR(j, i + 1, cur) if (intersect(arr[i], arr[j])) {
                ok[i] = false;
                ok[j] = false;
            }
        }

        int ans = 0;
        FOR(i, 1, cur) ans += ok[i];
        cout << ans;
    }
}

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

    #define task ""
    if (fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }

    cin >> n;
    FOR(i, 1, n) p[i].input();

    if (subtask1 :: check()) return subtask1 :: solve(), 0;
    subtask1 :: solve();

    return 0;
}

/* Discipline - Calm */

Compilation message (stderr)

geometrija.cpp: In function 'int main()':
geometrija.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
geometrija.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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