oj.uz

답안 #537582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537582 2022-03-15T09:17:01 Z Hydroxic_Acid Planine (COCI21_planine) C++17
0 / 110
 10 ms 1104 KB 
#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 == 0){
			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 == 0){
			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[(int)idx/2 - 1].second = curr;
		idx--;
	}
	
	sort(arr2.begin(), arr2.end(), comp);
	int cnt = 1;
	double eest = arr2[0].second;
	//cout << arr2[0].first << " " << arr2[0].second << "\n";
	for(int i = 1; i < (int)arr2.size(); i++){
		//cout << arr2[i].first << " " << arr2[i].second << "\n";
		if(arr2[i].first <= eest) continue;
		eest = arr2[i].second; cnt++;
	}
	cout << cnt;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 1104 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 564 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 1104 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -