Submission #1299278

#TimeUsernameProblemLanguageResultExecution timeMemory
1299278SamNguyenGeometrija (COCI21_geometrija)C++20
20 / 110
1036 ms576 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 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...