Submission #373300

#	Time	Username	Problem	Language	Result	Execution time	Memory
373300		rk42745417	Planine (COCI21_planine)	C++17	0 / 110	65 ms	1260 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define EMT ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 2e18;
const double EPS = 1e-9;

inline bool operator<(pair<ll, ll> &a, pair<ll, ll> &b) { return a.first * b.second < b.first * a.second; }
inline bool operator>(pair<ll, ll> &a, pair<ll, ll> &b) { return a.first * b.second > b.first * a.second; }

using fac = pair<ll, ll>;
signed main() { EMT
	int n;
	ll h;
	cin >> n >> h;
	vector<ll> x(n), y(n);
	vector<pair<ll, ll>> l(n, {-LINF, 1}), r(n, {LINF, 1});
	vector<pair<fac, fac>> line;
	for(int i = 0; i < n; i++)
		cin >> x[i] >> y[i];
	for(int i = 2; i + 1 < n; i += 2) {
		for(int j = 1; j + 1 < n; j+=2) {
			if(x[j] < x[i])
				l[i] = max(l[i], {x[i] * (y[j] - y[i]) - (x[i] - x[j]) * (h - y[i]), y[j] - y[i]});
			else
				r[i] = min(r[i], {x[i] * (y[j] - y[i]) + (x[j] - x[i]) * (h - y[i]), y[j] - y[i]});
		}
		line.push_back({l[i], r[i]});
		//cout << double(l[i].first) / l[i].second << '\n';
	}
	sort(line.begin(), line.end(), [&](const auto &a, const auto &b) { return a.second < b.second;});
	vector<bool> has(line.size());
	int ans = 0;
	//for(int i = 0; i < line.size(); i++)
		//cout << double(line[i].first.first) / line[i].first.second << ' ' << double(line[i].second.first) / line[i].second.second << '\n';
	for(int i = 0; i < line.size(); i++) {
		if(has[i])
			continue;
		for(int j = 0; j < line.size(); j++)
			if(!has[j] && !(line[j].first > line[i].second))
				has[j] = 1;
		ans++;
	}
	cout << ans << '\n';
}
/*
9 6
0 0
1 2
3 0
6 3
8 1
9 2
11 1
12 4
14 0

9 5
-5 2
-4 3
-2 1
0 4
2 2
3 3
4 1
5 2
6 1

*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long int, long int>, std::pair<long int, long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i = 0; i < line.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
Main.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long int, long int>, std::pair<long int, long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int j = 0; j < line.size(); j++)
      |                  ~~^~~~~~~~~~~~~

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