题目
传送门:QWQ
分析
在下面维护一个凸壳
好久没写博客了......
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=;
const double eps=1e-,INF=1e10;
struct Line{
double a,b;int n;
}l[maxn];
Line st[maxn];int top=;
bool cmp(Line a,Line b){
if(fabs(a.a-b.a)<eps)return a.b<b.b;
return a.a<b.a;
}
bool cmp2(Line a,Line b){ return a.n<b.n; }
double cross(Line x,Line y){//交点的x值
return (y.b-x.b)/(x.a-y.a);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%lf%lf",&l[i].a,&l[i].b);
l[i].n=i;
}
sort(l+,l++n,cmp); for(int i=;i<=n;i++){
// printf("--- %d\n",top);
while((top> && cross(st[top-],st[top])>=cross(st[top-],l[i]) ) || (top> && fabs(st[top].a-l[i].a)<eps)){
top--;
}
st[++top]=l[i];
} sort(st+,st++top,cmp2);
for(int i=;i<=top;i++) printf("%d ",st[i].n);
return ;
}