Submission #537580

#TimeUsernameProblemLanguageResultExecution timeMemory
537580Hydroxic_AcidPlanine (COCI21_planine)C++17
0 / 110
11 ms596 KiB
#include <iostream> #include <algorithm> #include <vector> using namespace std; #define int long long double n, h; vector<pair<double, double> > arr; vector<pair<double, double> > arr2; pair<double, double> stackk[1000000]; bool comp(pair<double, double> i1, pair<double, double> i2){ return i1.second<i2.second; } signed main(){ cin >> n >> h; if(n == 3){ cout << 0; return 0; } for(int i = 0; i < n; i++){ double x, y; cin >> x >> y; if(i == 0 || i == n - 1) continue; arr.push_back(make_pair(x, y)); } int idx = 0; int endpt = -1; while(idx < (int)arr.size() - 1){ if(idx % 2){ while(endpt != -1 && stackk[endpt].second <= arr[idx].second)endpt--; stackk[++endpt] = arr[idx]; idx++; continue; } double curr = arr[idx].first - ((h - arr[idx].second) * (arr[idx].first - stackk[endpt].first)/(stackk[endpt].second - arr[idx].second)); int i = endpt-1; while(i != -1 && curr < stackk[i].first){ curr = max(curr, arr[idx].first - ((h - arr[idx].second) * (arr[idx].first - stackk[i].first)/(stackk[i].second - arr[idx].second))); i--; } arr2.push_back(make_pair(curr, 0)); idx++; } idx = (int)arr.size() - 1; endpt = -1; while(idx > 0){ if(idx % 2){ while(endpt != -1 && stackk[endpt].second <= arr[idx].second)endpt--; stackk[++endpt] = arr[idx]; idx--; continue; } double curr = arr[idx].first + ((h - stackk[endpt].second) * (stackk[endpt].first - arr[idx].first)/(arr[idx].second - stackk[endpt].second)); int i = endpt-1; while(i != -1 && curr > stackk[i].first){ curr = min(curr, arr[idx].first + ((h - stackk[i].second) * (stackk[i].first - arr[idx].first)/(arr[idx].second - stackk[i].second))); i--; } arr2[idx/2 - 1].second = curr; idx--; } /* arr[(int)arr.size() - 1].second = prex + ((h - prey) * (x - prex) / (y - prey)); arr.push_back(make_pair(x - ((h - y) * (x - prex)/(prey - y)), 0)); */ sort(arr2.begin(), arr2.end(), comp); int cnt = 1; double eest = arr2[0].second; //cout << arr[0].first << " " << arr[0].second << "\n"; for(int i = 1; i < (int)arr2.size(); i++){ //cout << arr[i].first << " " << arr[i].second << "\n"; if(arr2[i].first <= eest) continue; eest = arr2[i].second; cnt++; } cout << cnt; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...