Submission #373040

#	Time	Username	Problem	Language	Result	Execution time	Memory
373040		sam571128	Planine (COCI21_planine)	C++14	0 / 110	3 ms	752 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e6+5;
const double EPS = 1e-7;
pair<double,double> seg[N];
int st[N], id[N];
int n, h;
double findp(int x1, int y1, int x2, int y2){
	assert(y1!=y2);
	return 1.0*(h-y1)*(x2-x1)/(y2-y1)+x1;
}

signed main(){
	fastio
	cin >> n >> h;
	vector<pair<double,double>> v(1);
	for(int i = 1;i <= n;i++){
		int x,y;
		cin >> x >> y;
		v.push_back({x,y});
	}
    for (int i = 3; i <= n; i+=2) {
        seg[i/2].first = findp(v[i].first,v[i].second, v[i-1].first, v[i-1].second);
    }
    for (int i = n-2; i >= 1; i-=2) {
        seg[i/2].second = findp(v[i].first,v[i].second, v[i+1].first, v[i+1].second);
    }
    sort(seg+1,seg+(n-2)/2,[&](pair<double,double> a, pair<double,double> b){
    	return a.second < b.second;
    });
    double tmp = seg[0].second;
    int ans = 1;

    for (int i = 1; i <= n / 2 - 1; ++i) {
        if (tmp >= seg[i].first)
            continue;

        tmp = seg[i].second;
        ++ans;
    }
    cout << ans << "\n";
}

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