#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18;
const ll INF = 1e15;
const ll MAXN = 2100;
struct P {
int x, y;
void read() {
cin >> x >> y;
}
bool operator <(P b) {
return make_pair(x, y) < make_pair(b.x, b.y);
}
P operator -(P other) {
return P{x - other.x, y - other.y};
}
ll operator *(P other) {
return x * other.y - y * other.x;
}
ll comp(P A, P B) {
return (A - *this) * (B - *this);
}
};
int main() {
fast
int n;
cin >> n;
if (n == 2) {
cout << "1\n";
return 0;
}
vector<P> points;
for (int i = 0; i < n; i++) {
P newP;
newP.read();
points.push_back(newP);
}
sort(points.begin(), points.end());
vector<P> hull, hull_now;
for (int rep = 0; rep < 2; rep++) {
for (auto pnt : points) {
while (hull_now.size() >= 2) {
P A = hull_now.end()[-2];
P B = hull_now.end()[-1];
if (A.comp(B, pnt) <= 0)
break;
hull_now.pop_back();
}
hull_now.push_back(pnt);
}
hull_now.pop_back();
for (auto u : hull_now)
hull.push_back(u);
hull_now.clear();
reverse(points.begin(), points.end());
}
if (hull.size() + 1 == n)
cout << 2 * hull.size() << "\n";
else
cout << hull.size() << "\n";
}
Compilation message
geometrija.cpp: In function 'int main()':
geometrija.cpp:70:22: warning: comparison of integer expressions of different signedness: 'std::vector<P>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | if (hull.size() + 1 == n)
| ~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
