#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
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++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
1260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
1260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
