题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
不同题目对于处于一条直线有不同要求,在更新栈顶那里要处理一下,如果叉积是0,就加到栈里边,用Andrew求凸包的时候,是当新的点在栈顶的线段的逆时针方向才更新栈顶,所以次top与top的线段和次top与新的点的线段的叉积应该是大于0的时候更新
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N=2e5+10;
typedef pair<double,double> pdd;
pdd q[N];
int stk[N];
bool used[N];
int 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-a.y*b.x;
}
double area(pdd a,pdd b,pdd c)
{
return cross(b-a,c-a);
}
double getdis(pdd a,pdd b)
{
double dx=a.x-b.x,dy=a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
double andrew()
{
sort(q,q+n);
int top=0;
for(int i=0;i<n;i++)
{
while(top>=2&&area(q[stk[top-1]],q[stk[top]],q[i])>0)
{
if(area(q[stk[top-1]],q[stk[top]],q[i])>0) used[stk[top--]]=false;
}
stk[++top]=i;
used[i]=true;
}
used[0]=false;
for(int i=n-1;i>=0;i--)
{
if(used[i]) continue;
while(top>=2&&area(q[stk[top-1]],q[stk[top]],q[i])>0)
top--;
stk[++top]=i;
}
double res=0;
for(int i=2;i<=top;i++)
res+=getdis(q[stk[i-1]],q[stk[i]]);
return res;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%lf%lf",&q[i].x,&q[i].y);
double res=andrew();
printf("%.2lf\n",res);
return 0;
}
先求的是上凸壳