Submission #950282

#	Time	Username	Problem	Language	Result	Execution time	Memory
950282		vjudge1	Planine (COCI21_planine)	C++17	0 / 110	3 ms	600 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define size(x) (int)x.size()
#define all(x) x.begin(), x.end()

template<class S, class T>
bool chmin(S& a, const T& b) {
  return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S& a, const T& b) {
  return a < b ? (a = b) == b : false;
}

struct fraction {
  int a, b;
};

void simplify(fraction& f) {
  int g = __gcd(f.a, f.b);
  f.a /= g;
  f.b /= g;
}
void add(fraction& A, const fraction B) {
  A.a *= B.b;
  A.a += B.a * A.b;
  A.b *= B.b;
  simplify(A);
}
void subtract(fraction& A, const fraction B) {
  A.a *= B.b;
  A.a -= B.a * A.b;
  A.b *= B.b;
  simplify(A);
}
void multiply(fraction& A, const fraction B) {
  A.a *= B.a;
  A.b *= B.b;
  simplify(A);
}
void divide(fraction& A, const fraction B) {
  A.a *= B.b;
  A.b *= B.a;
  simplify(A);
}

fraction find_x(fraction m, fraction c, int y) {
  fraction x = {y, 1};
  subtract(x, c);
  divide(x, m);
  return x;
}

fraction triangle_area(fraction x1, int y1, int x2, int y2, int x3, int y3) {
  fraction res1 = {x2, 1};
  subtract(res1, x1);
  fraction res2 = {y3 - y1, 1};
  fraction res3 = {y2 - y1, 1};
  fraction res4 = {x3, 1};
  subtract(res4, x1);
  multiply(res1, res2);
  multiply(res3, res4);
  subtract(res1, res3);
  return res1;
}
bool clockwise(fraction x1, int y1, int x2, int y2, int x3, int y3) {
  fraction f = triangle_area(x1, y1, x2, y2, x3, y3);
  return f.a == 0 || (f.a < 0 && f.b > 0) || (f.a > 0 && f.b < 0);
}
bool can(fraction x1, int y1, int x2, int y2, int x3, int y3) {
  return clockwise(x1, y1, x2, y2, x3, y3);
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, h;
  cin >> n >> h;
  int x[n], y[n];
  for (int i = 0; i < n; ++i) {
    cin >> x[i] >> y[i];
  }
  int res = 0;
  for (int i = 2; i < n - 1; i += 2) {
    res++;
    fraction m = {y[i] - y[i + 1], x[i] - x[i + 1]};
    simplify(m);
    fraction c = {y[i + 1] * x[i] - y[i] * x[i + 1], x[i] - x[i + 1]};
    simplify(c);
    fraction X = find_x(m, c, h);
    simplify(X);
    int j = i;
    while (j + 3 < n && can(X, h, x[j + 2], y[j + 2], x[j + 1], y[j + 1])) {
      j += 2;
    }
    i = j;
  }
  cout << res;
}

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