#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
struct Fraction{
ll p, q;
Fraction(ll _p = 0, ll _q = 1){
p = _p;
q = _q;
assert(q != 0);
if (q < 0){
p = -p;
q = -q;
}
ll g = abs(__gcd(p, q));
p /= g;
q /= g;
}
bool operator == (const Fraction &oth) const {
return (p == oth.p && q == oth.q);
}
bool operator < (const Fraction &oth) const {
return ((long double) p * oth.q < (long double) oth.p * q);
}
bool operator <= (const Fraction &oth) const {
return (oth == (*this) || (*this) < oth);
}
};
struct Point{
int x, y;
Point(int _x = 0, int _y = 0){
x = _x;
y = _y;
}
Point operator - (const Point &oth) const {
return Point(x - oth.x, y - oth.y);
}
ll operator * (const Point &oth) const {
return (ll) x * oth.y - (ll) y * oth.x;
}
};
struct Line{
ll a, b, c;
Line(ll _a, ll _b, ll _c){
a = _a;
b = _b;
c = _c;
}
Line(const Point &A, const Point &B){
a = A.y - B.y;
b = B.x - A.x;
c = (ll) A.x * B.y - (ll) A.y * B.x;
}
};
int n, h;
Point p[N];
int findOrientation(const Point &A, const Point &B, const Point &C){
ll x = (B - A) * (C - B);
if (x < 0)
return -1;
else if (x == 0)
return 0;
else
return 1;
}
Fraction findXCoor(const Line &d1, const Line &d2){
ll D = d1.a * d2.b - d2.a * d1.b;
ll Dx = -d1.c * d2.b + d2.c * d1.b;
assert(D != 0);
return Fraction(Dx, D);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("inp.txt", "r", stdin);
cin >> n >> h;
for(int i = 1; i <= n; i++)
cin >> p[i].x >> p[i].y;
Line d(0, 1, -h);
vector<pair<Fraction, Fraction>> segments(n / 2 - 1);
vector<Point> cvh;
for(int i = 1; i <= n; i++){
while (cvh.size() > 1 && findOrientation(cvh[cvh.size() - 2], cvh[cvh.size() - 1], p[i]) > -1)
cvh.pop_back();
if (i % 2 && 3 <= i && i <= n - 2)
segments[i / 2 - 1].first = findXCoor(Line(p[i], cvh.back()), d);
cvh.push_back(p[i]);
}
for(int i = n; i >= 1; i--){
while (cvh.size() > 1 && findOrientation(cvh[cvh.size() - 2], cvh[cvh.size() - 1], p[i]) < 1)
cvh.pop_back();
if (i % 2 && 3 <= i && i <= n - 2)
segments[i / 2 - 1].second = findXCoor(Line(p[i], cvh.back()), d);
cvh.push_back(p[i]);
}
vector<int> ok(segments.size());
int answer = 0;
while(true){
Fraction minX = Fraction(1e18, 1);
bool stop = 1;
for(int i = 0; i < (int) segments.size(); i++)
if (!ok[i]){
stop = 0;
minX = min(minX, segments[i].second);
}
if (stop)
break;
answer++;
for(int i = 0; i < (int) segments.size(); i++)
if (segments[i].first <= minX && minX <= segments[i].second)
ok[i] = 1;
}
cout << answer;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:85:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
85 | freopen("inp.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
16492 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
16492 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
16492 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
