#include <bits/stdc++.h>
using namespace std;
#define int long long
#define size(x) (int)x.size()
#define all(x) x.begin(), x.end()
template<class S, class T>
bool chmin(S& a, const T& b) {
return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S& a, const T& b) {
return a < b ? (a = b) == b : false;
}
struct fraction {
int a, b;
};
void simplify(fraction& f) {
int g = __gcd(f.a, f.b);
f.a /= g;
f.b /= g;
}
void add(fraction& A, const fraction B) {
A.a *= B.b;
A.a += B.a * A.b;
A.b *= B.b;
simplify(A);
}
void subtract(fraction& A, const fraction B) {
A.a *= B.b;
A.a -= B.a * A.b;
A.b *= B.b;
simplify(A);
}
void multiply(fraction& A, const fraction B) {
A.a *= B.a;
A.b *= B.b;
simplify(A);
}
void divide(fraction& A, const fraction B) {
A.a *= B.b;
A.b *= B.a;
simplify(A);
}
fraction find_x(fraction m, fraction c, int y) {
fraction x = {y, 1};
subtract(x, c);
divide(x, m);
return x;
}
fraction triangle_area(fraction x1, int y1, int x2, int y2, int x3, int y3) {
fraction res1 = {x2, 1};
subtract(res1, x1);
fraction res2 = {y3 - y1, 1};
fraction res3 = {y2 - y1, 1};
fraction res4 = {x3, 1};
subtract(res4, x1);
multiply(res1, res2);
multiply(res3, res4);
subtract(res1, res3);
return res1;
}
bool clockwise(fraction x1, int y1, int x2, int y2, int x3, int y3) {
fraction f = triangle_area(x1, y1, x2, y2, x3, y3);
return f.a == 0 || (f.a < 0 && f.b > 0) || (f.a > 0 && f.b < 0);
}
bool can(fraction x1, int y1, int x2, int y2, int x3, int y3) {
return clockwise(x1, y1, x2, y2, x3, y3);
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, h;
cin >> n >> h;
int x[n], y[n];
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i];
}
int res = 0;
for (int i = 2; i < n - 1; i += 2) {
res++;
fraction m = {y[i] - y[i + 1], x[i] - x[i + 1]};
simplify(m);
fraction c = {y[i + 1] * x[i] - y[i] * x[i + 1], x[i] - x[i + 1]};
simplify(c);
fraction X = find_x(m, c, h);
simplify(X);
int j = i;
while (j + 3 < n && can(X, h, x[j + 2], y[j + 2], x[j + 1], y[j + 1])) {
j += 2;
}
i = j;
}
cout << res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
