Submission #1152649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152649		jmuzhen	Geometrija (COCI21_geometrija)	C++20	0 / 110	1 ms	320 KiB

geometrija

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

#define double long double
#define int long long

constexpr double INF = 1e18;

constexpr double EPSILON = LDBL_EPSILON;

struct Point
{
  int x, y;
};

struct Line {
  double m, c; // to define the line: y = mx+c
  double s, e; // to define the start and end x-value of segment
};

bool eq(double a, double b) {
  return abs(a-b) <= EPSILON;
}
bool le(double a, double b) {
  return !eq(a,b) && b - a > 0;
}
bool ge(double a, double b) {
  return !eq(a,b) && a - b > 0;
}

Line to_line(Point a, Point b) {
  if (a.x > b.x) swap(a,b); // ensure a.x <= b.x

  Line l;
  if (eq(a.x, b.x)) {
    l.m = INF;
    // special line. the c value is the x value and
    // s,e are the y values instead of x.
    l.c = a.x;
    l.s = a.y; l.e = b.y;
  }
  else {
    l.m = (double)(a.y - b.y) / (double)(a.x - b.x);
    // y = mx+c so c = y - mx
    l.c = a.y - l.m * a.x;
  }
  l.s = a.x; l.e = b.x;

  return l;
}

double intersect(Line a, Line b) {
  // is the math correct idk. to check
  return (double)(a.c - b.c)/(double)(b.m - a.m);
}

bool cross(Line a, Line b) {
  if (a.m == INF || b.m == INF) {
    if (a.m == INF) swap(a, b);
    // b is guaranteed to be vertical
    if (a.m == INF) {
      // both are vertical
      return le(a.e, b.s) || le(b.e, a.s);
    }
    else {
      // b is vertical but a is not
      // so we see if 1) a passes through the x value of b; and 2)
      // to see if a at that value of x is on b.
      bool condition1 = le(a.s, b.c) && le(b.c, a.e);
      int yval = (a.m * b.c + a.c);
      bool condition2 = le(b.s, yval) && le(yval, b.e);
      return (condition1 && condition2);
    }
  }
  else {
    // normal case
    // find intersection point
    double x = intersect(a, b);
    // check if it's on a and on b
    bool condition1 = le(a.s, x) && le(x, a.e);
    bool condition2 = le(b.s, x) && le(x, b.e);
    return (condition1 && condition2);
  }
}

vector<Point> points;
vector<Line> lines;

signed main() {
  int n; cin >> n;
  for (int i = 0; i < n; i++) {
    int x, y; cin >> x >> y;
    Point p = {x,y};
    points.push_back(p);
  }

  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      Line l = to_line(points[i], points[j]);
      lines.push_back(l);
    }
  }

  int ans = 0;
  for (int i = 0; i < lines.size(); i++) {
    bool ok = true;
    for (int j = i+1; j < lines.size(); j++) {
      if (cross(lines[i], lines[j])) {
        ok = false;
        break;
      }
    }
    if (ok) {
      ans++;
    }
  }

  cout << ans << endl;
}

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