| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 538551 |
2022-03-17T04:45:47 Z |
hmm789 |
Planine (COCI21_planine) |
C++14 |
|
282 ms |
35172 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const double EPS = 1e-9;
int n, h;
struct point {
int x, y;
};
struct hull {
deque<point> dq;
int dir;
int getdir(point a, point b, point c) {
int tmp = a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
if(tmp > 0) return 0;
else if(tmp < 0) return 1;
else return 2;
}
void insert(point x) {
while(dq.size() > 1) {
int s = dq.size();
if(getdir(dq[s-2], dq[s-1], x) != dir) dq.pop_back();
else break;
}
dq.push_back(x);
}
double query(point x) {
while(dq.size() > 1) {
int s = dq.size();
if(getdir(dq[s-2], dq[s-1], x) != dir) dq.pop_back();
else break;
}
point a = dq.back();
return (h-x.y)*1.0*(a.x-x.x)/(a.y-x.y)+x.x;
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int ans = 0, idx;
double last = -1e18;
cin >> n >> h;
point pt[n];
pair<double, double> pos[n/2-1];
idx = n/2-2;
for(int i = 0; i < n; i++) cin >> pt[i].x >> pt[i].y;
hull left, right;
left.dir = 0, right.dir = 1;
for(int i = n-2; i >= 3; i -= 2) {
left.insert(pt[i]);
pos[idx].first = left.query(pt[i-1]);
idx--;
}
idx = 0;
for(int i = 1; i < n-2; i += 2) {
right.insert(pt[i]);
pos[idx].second = right.query(pt[i+1]);
idx++;
}
sort(pos, pos+n/2-1);
for(int i = 0; i < n/2-1; i++) {
if(pos[i].second > last+EPS) {
ans++;
last = pos[i].first;
}
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
720 KB |
Output is correct |
| 2 |
Correct |
3 ms |
752 KB |
Output is correct |
| 3 |
Correct |
3 ms |
724 KB |
Output is correct |
| 4 |
Correct |
20 ms |
4436 KB |
Output is correct |
| 5 |
Correct |
23 ms |
4648 KB |
Output is correct |
| 6 |
Correct |
25 ms |
4792 KB |
Output is correct |
| 7 |
Correct |
202 ms |
34448 KB |
Output is correct |
| 8 |
Correct |
225 ms |
34360 KB |
Output is correct |
| 9 |
Correct |
237 ms |
34184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
324 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
720 KB |
Output is correct |
| 2 |
Correct |
3 ms |
752 KB |
Output is correct |
| 3 |
Correct |
3 ms |
724 KB |
Output is correct |
| 4 |
Correct |
20 ms |
4436 KB |
Output is correct |
| 5 |
Correct |
23 ms |
4648 KB |
Output is correct |
| 6 |
Correct |
25 ms |
4792 KB |
Output is correct |
| 7 |
Correct |
202 ms |
34448 KB |
Output is correct |
| 8 |
Correct |
225 ms |
34360 KB |
Output is correct |
| 9 |
Correct |
237 ms |
34184 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
324 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
324 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
320 KB |
Output is correct |
| 17 |
Correct |
215 ms |
35108 KB |
Output is correct |
| 18 |
Correct |
227 ms |
35172 KB |
Output is correct |
| 19 |
Correct |
23 ms |
4644 KB |
Output is correct |
| 20 |
Correct |
240 ms |
34356 KB |
Output is correct |
| 21 |
Correct |
24 ms |
4440 KB |
Output is correct |
| 22 |
Correct |
227 ms |
34296 KB |
Output is correct |
| 23 |
Correct |
1 ms |
324 KB |
Output is correct |
| 24 |
Correct |
229 ms |
34268 KB |
Output is correct |
| 25 |
Correct |
23 ms |
4564 KB |
Output is correct |
| 26 |
Correct |
282 ms |
34480 KB |
Output is correct |
| 27 |
Correct |
12 ms |
2376 KB |
Output is correct |
