Submission #382786

#TimeUsernameProblemLanguageResultExecution timeMemory
382786ne4eHbKaPlanine (COCI21_planine)C++17
0 / 110
2091 ms3304 KiB
#include <bits/stdc++.h> using namespace std; #ifndef _LOCAL //#pragma GCC optimize("O3,Ofast") #else #pragma GCC optimize("O0") #endif template<typename t> inline void umin(t &a, const t b) {a = min(a, b);} template<typename t> inline void umax(t &a, const t b) {a = max(a, b);} typedef pair<int, int> pii; typedef long long ll; typedef long double ld; typedef int8_t byte; ll time() {return chrono::system_clock().now().time_since_epoch().count();} mt19937 rnd(time()); #define ft first #define sd second #define len(f) int((f).size()) #define bnd(f) (f).begin(), (f).end() #define _ <<' '<< const int inf = 1e9 + 5; const ll inf64 = 4e18 + 5; const int md = 998244353; namespace MD { void add(int &a, const int b) {if((a += b) >= md) a -= md;} void sub(int &a, const int b) {if((a -= b) < 0) a += md;} int prod(const int a, const int b) {return ll(a) * b % md;} }; const int N = 1e6 + 5; int h, x[N], y[N], n; vector<pair<ld, ld>> c; bool mk[N]; ld point(int i, int j) { return x[j] + (x[j] - x[i]) * ll(h - y[j]) / ld(y[j] - y[i]); } const ld eps = 1e-15; inline bool eq(const ld a, const ld b) {return abs(a - b) < eps;} inline bool le(const ld a, const ld b) {return a + eps < b;} void solve() { cin >> n >> h; for(int i = 0; i < n; ++i) cin >> x[i] >> y[i]; c.clear(); for(int i = 2; i + 1 < n; i += 2) c.push_back({point(i, i - 1), point(i, i + 1)}); sort(bnd(c)); n = len(c); memset(mk, 0, n); ld f; bool u = true; // for(int i = 1; i < n; ++i) // mk[i] = eq(c[i].ft, c[i - 1].ft); // for(int i = n - 1; ~i; --i) { // if(mk[i]) // continue; // if(!u && !le(c[i].sd, f)) // mk[i] = true; // if(u || c[i].sd < f) // f = c[i].sd, // u = false; // } for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { if(i == j) continue; if(!le(c[j].ft, c[i].ft) && !le(c[i].sd, c[j].sd)) mk[i] = true; } } int ans {}; u = true; for(int i = 0; i < n; ++i) { if(mk[i]) continue; if(u || le(f, c[i].ft)) f = c[i].sd, ++ans, u = false; } cout << ans << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef _LOCAL // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); #else system("color a"); freopen("in.txt", "r", stdin); int t; cin >> t; while(t--) #endif solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...