凸包模板
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1e5+10;
typedef pair<double,double> PDD;
vector<PDD> alls;
int n;
bool used[N];
PDD operator-(PDD a,PDD b){
return {a.x-b.x,a.y-b.y};
}
double cross(PDD a,PDD b){
return a.x*b.y-b.x*a.y;
}
double area(PDD a,PDD b,PDD c){
return cross(b-a,c-a);
}
int main(){
cin>>n;
for(int i = 1;i<=n;i++){
double x,y;
cin>>x>>y;
alls.push_back({x,y});
}
sort(alls.begin(),alls.end());
int stk[N];
int tt = 0;
for(int i = 0;i<n;i++){
while(tt>=2&&area(alls[stk[tt-1]],alls[stk[tt]],alls[i])>=0)used[stk[tt--]] = false;
stk[++tt] = i;
used[i] = true;
}
used[0] = false;
for(int i = n-1;i>=0;i--){
if(used[i]) continue;
while(tt>=2&&area(alls[stk[tt-1]],alls[stk[tt]],alls[i])>=0)tt--;
stk[++tt] = i;
}
}