模板收集

计算几何

namespace Geometry{using db=double;struct Point{db x,y;};struct vec{db x,y;vec(db a,db b){x=a,y=b;}vec(Point t){x=t.x,y=t.y;}vec operator-(const vec &t){return {x-t.x,y-t.y};}};db cross(vec x,vec y){return x.x*y.y-x.y*y.x;}db Side(Point x,Point y,Point z){return cross((vec)y-x,(vec)z-x);}db dis(Point x,Point y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}vector<Point>Andrew(vector<Point>a){if(a.size()<=3) return a;vector<Point>A;sort(a.begin(),a.end(),[](Point x,Point y){return x.x==y.x?x.y<y.y:x.x<y.x;});A.assign(a.begin(),a.begin()+2);for(int i=2;i<a.size();i++){for(;A.size()>=2&&Side(A[A.size()-2],A.back(),a[i])<=0;A.pop_back());A.emplace_back(a[i]);}for(int i=a.size()-2,siz=A.size();~i;i--){for(;A.size()>siz&&Side(A[A.size()-2],A.back(),a[i])<=0;A.pop_back());A.emplace_back(a[i]);}if(A.size()>1) A.pop_back();return A;}
}