Submission #522757

#TimeUsernameProblemLanguageResultExecution timeMemory
522757nhphucqtLightning Rod (NOI18_lightningrod)C++17
80 / 100
2031 ms246288 KiB
#include <bits/stdc++.h>

using namespace std;

struct Point {
	int x, y;
	Point() {}
	Point(int _x, int _y) {
		x = _x; y = _y;
	}
};

const int N = 1e7+7;
int numPoint, sz;
Point points[N], st[N];

bool inside(const Point &a, const Point &b) { // check if a is inside b
	return abs(b.x - a.x) <= b.y - a.y;
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	#ifdef NHPHUCQT
	freopen("demo.inp", "r", stdin);
	freopen("demo.out", "w", stdout);
	#endif // NHPHUCQT

	cin >> numPoint;
	for (int i = 0; i < numPoint; ++i) {
		cin >> points[i].x >> points[i].y;
	}
	for (int i = 0, cnt = 0, maxs = 0; i < numPoint; ++i) {
		cnt++; maxs = max(maxs, points[i].y);
		if (i + 1 == numPoint || points[i].x != points[i+1].x) {
			while (sz > 0 && inside(st[sz-1], Point(points[i].x, maxs))) {
				sz--;
			}
			if (sz == 0 || !inside(Point(points[i].x, maxs), st[sz-1])) {
				st[sz++] = points[i];
			}
			cnt = maxs = 0;
		}
	}
	cout << sz;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...