WA15,16,23,27求助
查看原帖
WA15,16,23,27求助
989792
lrx___楼主2025/6/17 09:13

使用叉积求凸包,使用差分约束求线段覆盖,用拓扑排序求差分约束。

#ifdef LOCAL_TEST
#include "D:/C++/include/all.h"
#else
#define debug(...)
#define cpp_version_ __cplusplus
#endif
#include <bits/stdc++.h>
#undef cpp_version_

using namespace std;
using bool_t = unsigned char;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;

void fast_io() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
template <typename T> void ckmax(T &a, T b) {
  if (a < b) a = b;
}
template <typename T> void ckmin(T &a, T b) {
  if (b < a) a = b;
}

constexpr f64 eps = 1e-6;

struct Point {
  int x, y;
  Point operator-(const Point& o) const {
    return {x - o.x, y - o.y};
  }
};
using Vec = Point;

i64 Cross(const Vec& a, const Vec& b) {
  return static_cast<i64>(a.x) * b.y - static_cast<i64>(a.y) * b.x;
}
void solve() {
  int N, H;
  cin >> N >> H;
  vector<Point> a(N);
  for (int i = 0; i < N; ++i) {
    cin >> a[i].x >> a[i].y;
  }

  vector<pair<f64, f64>> b((N >> 1) - 1);
  vector<Point> ch;
  u32 ch_len = 0;
  int cnt = 0;
  Point this_p;
  for (int i = 0; i < N; ++i) {
    this_p = a[i];
    while (ch_len > 1 && Cross(ch[ch_len - 1] - ch[ch_len - 2], this_p - ch[ch_len - 1]) >= 0) {
      ch.pop_back();
      --ch_len;
    }
    if (!(i & 1) && i != 0 && i != N - 1) {
      b[cnt++].first = this_p.x - (this_p.x - ch[ch_len - 1].x) * (H - this_p.y) / static_cast<f64>(ch[ch_len - 1].y - this_p.y);
    }
    ch.push_back(this_p);
    ++ch_len;
  }
  ch.clear(); ch_len = 0; cnt = (N >> 1) - 1;
  for (int i = N - 1; i >= 0; --i) {
    this_p = a[i];
    while (ch_len > 1 && Cross(ch[ch_len - 1] - ch[ch_len - 2], this_p - ch[ch_len - 1]) <= 0) {
      ch.pop_back();
      --ch_len;
    }
    if (!(i & 1) && i != 0 && i != N - 1) {
      b[--cnt].second = this_p.x + (ch[ch_len - 1].x - this_p.x) * (H - this_p.y) / static_cast<f64>(ch[ch_len - 1].y - this_p.y);
    }
    ch.push_back(this_p);
    ++ch_len;
  }
  vector<f64> nums;
  for (const auto& p : b) {
    nums.push_back(p.first);
    nums.push_back(p.second);
  }
  sort(nums.begin(), nums.end());
  nums.resize(N = unique(nums.begin(), nums.end(), [](f64 a, f64 b) {return fabs(a - b) < eps;}) - nums.begin());
  
  vector<vector<pair<int, int>>> g(N + 1);
  pair<int, int> range;
  for (const auto& p : b) {
    range = {
      lower_bound(nums.begin(), nums.end(), p.first, [](f64 a, f64 b){return a - b < -eps;}) - nums.begin() + 1,
      lower_bound(nums.begin(), nums.end(), p.second, [](f64 a, f64 b){return a - b < -eps;}) - nums.begin() + 1
    };
    g[range.first - 1].emplace_back(range.second, 1);
  }
  vector<int> dist(N + 1, 0);
  for (int i = 0; i < N; ++i) {
    g[i].emplace_back(i + 1, 0);
    for (const auto& [v, w] : g[i]) {
      ckmax(dist[v], dist[i] + w);
    }
  }
  cout << dist[N] << '\n';
}
int main() {
  fast_io();
  int T = 1;
  // cin >> T;
  while (T--) {
    solve();
#ifdef LOCAL_TEST
    cout << flush;
    // cerr << endl;
#endif
  }
  return 0;
}
2025/6/17 09:13
加载中...