它SPFA了
本地运行不了(
一进去就卡死
已知如下函数有误
若注释去此函数调用则可
求dalao查错/kel/kel/kel
Polygon HPI(Line *v,ll n){
for(ll i=0;i<n;i++) v[i].ang=Line_angle(v[i]);
sort(v,v+n);
Polygon ans;
Line q[maxp];
Point p[maxp];
ll l=0,r=0;
q[0]=v[0];
for(ll i=1;i<n;i++){
while(l<r&&!Onleft(v[i],p[r-1])) r--;
while(l<r&&!Onleft(v[i],p[l])) l++;
q[++l]=v[i];
if(sgn(Cross(q[r].p2,q[l-1].p2))==0){
r--;
if(Onleft(q[r],v[i].p1)) q[r]=v[i];
}
if(l<r) p[r-1]=Cross_point(q[r-1].p1,q[r-1].p2+q[r-1].p1,q[r].p1,q[r].p2+q[r].p1);
}
while(l<r&&!Onleft(q[l],p[r-1])) r--;
if(r-l<=1) return ans;
p[r]=Cross_point(q[r].p1,q[r].p2+q[r].p1,q[l].p1,q[l].p2+q[l].p1);
for(ll i=l;i<=r;i++) ans.p[i-l]=p[i];
ans.n=r-l+1;
return ans;
}