Submission #538551

#	Time	Username	Problem	Language	Result	Execution time	Memory
538551		hmm789	Planine (COCI21_planine)	C++14	110 / 110	282 ms	35172 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define double long double

const double EPS = 1e-9;
int n, h;

struct point {
	int x, y;
};

struct hull {
	deque<point> dq;
	int dir;
	int getdir(point a, point b, point c) {
		int tmp = a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
		if(tmp > 0) return 0;
		else if(tmp < 0) return 1;
		else return 2;
	}
	void insert(point x) {
		while(dq.size() > 1) {
			int s = dq.size();
			if(getdir(dq[s-2], dq[s-1], x) != dir) dq.pop_back();
			else break;
		}
		dq.push_back(x);
	}
	double query(point x) {
		while(dq.size() > 1) {
			int s = dq.size();
			if(getdir(dq[s-2], dq[s-1], x) != dir) dq.pop_back();
			else break;
		}
		point a = dq.back();
		return (h-x.y)*1.0*(a.x-x.x)/(a.y-x.y)+x.x;
	}
};

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int ans = 0, idx;
  	double last = -1e18;
	cin >> n >> h;
	point pt[n];
	pair<double, double> pos[n/2-1];
	idx = n/2-2;
	for(int i = 0; i < n; i++) cin >> pt[i].x >> pt[i].y;
	hull left, right;
	left.dir = 0, right.dir = 1;
	for(int i = n-2; i >= 3; i -= 2) {
		left.insert(pt[i]);
		pos[idx].first = left.query(pt[i-1]);
		idx--;
	}
	idx = 0;
	for(int i = 1; i < n-2; i += 2) {
		right.insert(pt[i]);
		pos[idx].second = right.query(pt[i+1]);
		idx++;
	}
	sort(pos, pos+n/2-1);
	for(int i = 0; i < n/2-1; i++) {
		if(pos[i].second > last+EPS) {
			ans++;
			last = pos[i].first;
		}
	}
	cout << ans;
}

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