Submission #501549

#	Time	Username	Problem	Language	Result	Execution time	Memory
501549		wleung_bvg	Planine (COCI21_planine)	C++17	110 / 110	655 ms	62208 KiB

Main

#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int sz(const C&c){return int(c.size());}
using ll=long long;using ld=long double;constexpr const char nl='\n',sp=' ';

using T = long double;
constexpr const T EPS = 1e-9;
bool lt(T a, T b) { return a + EPS < b; }
bool le(T a, T b) { return !lt(b, a); }
bool gt(T a, T b) { return lt(b, a); }
bool ge(T a, T b) { return !lt(a, b); }
bool eq(T a, T b) { return !lt(a, b) && !lt(b, a); }
bool ne(T a, T b) { return lt(a, b) || lt(b, a); }
int sgn(T a) { return lt(a, 0) ? -1 : lt(0, a) ? 1 : 0; }
struct eps_lt { bool operator () (T a, T b) const { return lt(a, b); } };
struct eps_le { bool operator () (T a, T b) const { return !lt(b, a); } };
struct eps_gt { bool operator () (T a, T b) const { return lt(b, a); } };
struct eps_ge { bool operator () (T a, T b) const { return !lt(a, b); } };
struct eps_eq {
  bool operator () (T a, T b) const { return !lt(a, b) && !lt(b, a); }
};
struct eps_ne {
  bool operator () (T a, T b) const { return lt(a, b) || lt(b, a); }
};

#define OP(op, U, a, x, y) pt operator op (U a) const { return pt(x, y); } \
  pt &operator op##= (U a) { return *this = *this op a; }
#define CMP(op, body) bool operator op (pt p) const { return body; }
struct pt {
  T x, y; constexpr pt(T x = 0, T y = 0) : x(x), y(y) {}
  pt operator + () const { return *this; }
  pt operator - () const { return pt(-x, -y); }
  OP(+, pt, p, x + p.x, y + p.y) OP(-, pt, p, x - p.x, y - p.y)
  OP(*, T, a, x * a, y * a) OP(/, T, a, x / a, y / a)
  friend pt operator * (T a, pt p) { return pt(a * p.x, a * p.y); }
  bool operator < (pt p) const { return eq(x, p.x) ? lt(y, p.y) : lt(x, p.x); }
  CMP(<=, !(p < *this)) CMP(>, p < *this) CMP(>=, !(*this < p))
  CMP(==, !(*this < p) && !(p < *this)) CMP(!=, *this < p || p < *this)
  OP(*, pt, p, x * p.x - y * p.y, y * p.x + x * p.y)
  OP(/, pt, p, (x * p.x + y * p.y) / (p.x * p.x + p.y * p.y),
               (y * p.x - x * p.y) / (p.x * p.x + p.y * p.y))
};
#undef OP
#undef CMP
istream &operator >> (istream &stream, pt &p) { return stream >> p.x >> p.y; }
ostream &operator << (ostream &stream, pt p) {
  return stream << p.x << ' ' << p.y;
}
pt conj(pt a) { return pt(a.x, -a.y); }
T dot(pt a, pt b) { return a.x * b.x + a.y * b.y; }
T cross(pt a, pt b) { return a.x * b.y - a.y * b.x; }
T norm(pt a) { return dot(a, a); }
T abs(pt a) { return sqrt(norm(a)); }
T arg(pt a) { return atan2(a.y, a.x); }
pt polar(T r, T theta) { return r * pt(cos(theta), sin(theta)); }
T distSq(pt a, pt b) { return norm(b - a); }
T dist(pt a, pt b) { return abs(b - a); }
T ang(pt a, pt b) { return arg(b - a); }
// sign of ang, area2, ccw: 1 if counterclockwise, 0 if collinear,
//   -1 if clockwise
T ang(pt a, pt b, pt c) {
  a -= b; c -= b; return arg(pt(dot(c, a), cross(c, a)));
}
// twice the signed area of triangle a, b, c
T area2(pt a, pt b, pt c) { return cross(b - a, c - a); }
int ccw(pt a, pt b, pt c) { return sgn(area2(a, b, c)); }
// a rotated theta radians around p
pt rot(pt a, pt p, T theta) { return (a - p) * pt(polar(T(1), theta)) + p; }
// rotated 90 degrees ccw
pt perp(pt a) { return pt(-a.y, a.x); }

struct Line {
  pt v; T c;
  // ax + by = c, left side is ax + by > c
  Line(T a = 0, T b = 0, T c = 0) : v(b, -a), c(c) {}
  // direction vector v with offset c
  Line(pt v, T c) : v(v), c(c) {}
  // points p and q
  Line(pt p, pt q) : v(q - p), c(cross(v, p)) {}
  T eval(pt p) const { return cross(v, p) - c; }
  // sign of onLeft, dist: 1 if left of line, 0 if on line, -1 if right of line
  int onLeft(pt p) const { return sgn(eval(p)); }
  T dist(pt p) const { return eval(p) / abs(v); }
  T distSq(pt p) const { T e = eval(p); return e * e / norm(v); }
  // rotated 90 degrees ccw
  Line perpThrough(pt p) const { return Line(p, p + perp(v)); }
  Line translate(pt p) const { return Line(v, c + cross(v, p)); }
  Line shiftLeft(T d) const { return Line(v, c + d * abs(v)); }
  pt proj(pt p) const { return p - perp(v) * eval(p) / norm(v); }
  pt refl(pt p) const { return p - perp(v) * T(2) * eval(p) / norm(v); }
  // compares points by orthogonal projection (3 way comparison)
  int cmpProj(pt p, pt q) const { return sgn(dot(v, p) - dot(v, q)); }
};

int lineLineIntersection(Line l1, Line l2, pt &res) {
  T d = cross(l1.v, l2.v);
  if (eq(d, 0)) return l2.v * l1.c == l1.v * l2.c ? 2 : 0;
  res = (l2.v * l1.c - l1.v * l2.c) / d; return 1;
}

template <class T, class Cmp = less<T>>
vector<pair<T, T>> &maxDisjointIntervals(vector<pair<T, T>> &A,
                                         Cmp cmp = Cmp()) {
  sort(A.begin(), A.end(), [&] (const pair<T, T> &a, const pair<T, T> &b) {
    return cmp(a.second, b.second);
  });
  int i = 0; for (int l = 0, r = 0, N = A.size(); l < N; l = r, i++) {
    A[i] = A[l]; for (r = l + 1; r < N && !cmp(A[i].second, A[r].first); r++);
  }
  A.erase(A.begin() + i, A.end()); return A;
}

const bool FIRST = true, LAST = false;
template <const bool ISFIRST, class T, class F> T bsearch(T lo, T hi, F f) {
  static_assert(is_integral<T>::value, "T must be integral");
  hi--; while (lo <= hi) {
    T mid = lo + (hi - lo) / 2;
    if (f(mid) == ISFIRST) hi = mid - 1;
    else lo = mid + 1;
  }
  return ISFIRST ? lo : hi;
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // freopen("err.txt", "w", stderr);
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N;
  ld H;
  cin >> N >> H;
  Line l(pt(0, H), pt(1, H));
  vector<pt> P(N);
  for (auto &&p : P) cin >> p;
  vector<pair<T, T>> intervals;
  for (int i = 2; i < N - 2; i += 2) intervals.emplace_back(0, 0);
  vector<pt> hull;
  for (int i = 1; i < N - 2; i++) {
    if (i % 2) {
      while (sz(hull) >= 2 && ccw(hull[sz(hull) - 2], hull[sz(hull) - 1], P[i]) >= 0) hull.pop_back();
      hull.push_back(P[i]); 
    } else {
      int j = bsearch<FIRST>(0, sz(hull) - 1, [&] (int k) {
        return ccw(hull[k], hull[k + 1], P[i]) > 0;
      });
      pt p;
      lineLineIntersection(l, Line(hull[j], P[i]), p);
      intervals[i / 2 - 1].first = p.x;
    }
  }
  hull.clear();
  for (int i = N - 2; i >= 2; i--) {
    if (i % 2) {
      while (sz(hull) >= 2 && ccw(hull[sz(hull) - 2], hull[sz(hull) - 1], P[i]) <= 0) hull.pop_back();
      hull.push_back(P[i]); 
    } else {
      int j = bsearch<FIRST>(0, sz(hull) - 1, [&] (int k) {
        return ccw(hull[k], hull[k + 1], P[i]) < 0;
      });
      pt p;
      lineLineIntersection(l, Line(hull[j], P[i]), p);
      intervals[i / 2 - 1].second = p.x;
    }
  }
  cout << sz(maxDisjointIntervals(intervals, eps_lt())) << nl;
  return 0;
}

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