26 lines
581 B
C++
26 lines
581 B
C++
forr(i, now) vec.pb(A[i]);
|
|
sort(all(vec));
|
|
|
|
vll upper;
|
|
for(auto i:vec)
|
|
{
|
|
while(upper.size() >= 2 && ccw(upper[upper.size()-2], upper.back(), i) >= 0)
|
|
upper.pop_back();
|
|
upper.push_back(i);
|
|
}
|
|
|
|
reverse(all(vec));
|
|
vll lower;
|
|
for(auto i:vec)
|
|
{
|
|
while(lower.size() >= 2 && ccw(lower[lower.size()-2], lower.back(), i) >= 0)
|
|
lower.pop_back();
|
|
lower.push_back(i);
|
|
}
|
|
|
|
assert(upper.front() == lower.back() && lower.front() == upper.back());
|
|
upper.pop_back(); lower.pop_back();
|
|
|
|
vll hull;
|
|
hull.insert(hull.end(), all(upper));
|
|
hull.insert(hull.end(), all(lower)); |