procon

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub mugen1337/procon

:warning: Geometry/include.hpp

Depends on

Code

#include "./template.hpp"
#include "./Rotate.hpp"
#include "./Dot.hpp"
#include "./Cross.hpp"
#include "./CounterClockWise.hpp"
#include "./Projection.hpp"
#include "./Intersect.hpp"
#include "./Distance.hpp"
#include "./CrossPoint.hpp"
#include "./Angle.hpp"
#include "./InscribedCircle.hpp"
#include "./CircumscribedCircle.hpp"
#include "./Tangent.hpp"
#include "./Contain.hpp"
#include "./MinimumBoundingCircle.hpp"
#include "./ClosestPair.hpp"
#include "./Convex.hpp"
#line 1 "Geometry/template.hpp"
// Real
using Real=double;
const Real EPS=1e-6;
const Real pi=acosl(-1);

// Point
using Point=complex<Real>;
istream &operator>>(istream &is,Point &p){
    Real a,b;
    is>>a>>b;
    p=Point(a,b);
    return is;
}
ostream &operator<<(ostream &os,Point &p){
    return os<<fixed<<setprecision(12)<<p.real()<<' '<<p.imag();
}
inline bool eq(Real a,Real b){
    return fabs(a-b)<EPS;
}
Point operator*(const Point &p,const Real &d){
    return Point(real(p)*d,imag(p)*d);
}

// Line
struct Line{
    Point p1,p2;
    Line()=default;
    Line(Point p1,Point p2):p1(p1),p2(p2){}
    //Ax + By = C
    Line(Real A,Real B,Real C){
        if(eq(A,0))     p1=Point(0,C/B),p2=Point(1,C/B);
        else if(eq(B,0))p1=Point(C/A,0),p2=Point(C/A,1);
        else            p1=Point(0,C/B),p2=Point(C/A,0);
    }
};

// Segment
struct Segment:Line{
    Segment()=default;
    Segment(Point p1,Point p2):Line(p1,p2){}
};
struct Circle{
    Point center;
    Real r;
    Circle()=default;
    Circle(Point center,Real r):center(center),r(r){}
};

// Polygon
using Polygon=vector<Point>;
#line 1 "Geometry/Rotate.hpp"
Point rotate(Real theta,Point p){
    return Point(cos(theta)*real(p)-sin(theta)*imag(p),sin(theta)*real(p)+cos(theta)*imag(p));
}
#line 1 "Geometry/Dot.hpp"
// Dot
Real dot(Point a,Point b) {
    return real(a)*real(b)+imag(a)*imag(b);
}
#line 1 "Geometry/Cross.hpp"
// Cross
Real cross(Point a,Point b){
    return real(a)*imag(b)-imag(a)*real(b);
}
#line 1 "Geometry/CounterClockWise.hpp"
// ccw (counter clockwise) (Requires: cross, dot)
//https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_1_C
int ccw(Point a,Point b,Point c){
   b-=a;c-=a;
   if(cross(b,c)>EPS)       return  1;//COUNTER CLOCKWISE
   else if(cross(b,c)<-EPS) return -1;//CLOCKWISE
   else if(dot(b,c)<0)      return  2;//c--a--b ONLINE BACK
   else if(norm(b)<norm(c)) return -2;//a--b--c ONLINE FRONT
   else                     return  0;//a--c--b ON SEGMENT
}
#line 1 "Geometry/Projection.hpp"
// Projection (Requires: dot)
Point projection(Line l,Point p){
    // ベクトルl乗に点pからおろした垂線の足
    Real k=dot(l.p1-l.p2,p-l.p1)/norm(l.p1-l.p2);
    return l.p1+(l.p1-l.p2)*k;
}
Point projection(Segment l,Point p){
    Real k=dot(l.p1-l.p2,p-l.p1)/norm(l.p1-l.p2);
    return l.p1+(l.p1-l.p2)*k;
}
#line 1 "Geometry/Intersect.hpp"
// Intersect (Requires : ccw, Dots, Cross, Projection)
bool intersect(Line l,Point p){
    return abs(ccw(l.p1,l.p2,p))!=1;
}
//直線の交差判定，外積
bool intersect(Line l1,Line l2){
    return abs(cross(l1.p2-l1.p1,l2.p2-l2.p1))>EPS or abs(cross(l1.p2-l1.p1,l2.p2-l1.p1))<EPS;
}
//線分に点が乗るかの判定，ccw
bool intersect(Segment s,Point p){
    return ccw(s.p1,s.p2,p)==0;
}
//直線と線分の交差判定
bool intersect(Line l,Segment s){
    return cross(l.p2-l.p1,s.p1-l.p1)*cross(l.p2-l.p1,s.p2-l.p1)<EPS;
}
//円と直線の交差判定
bool intersect(Circle c,Line l){
    return abs(c.center-projection(l,c.center))<=c.r+EPS;
}
//円上かどうか，内部かどうかではない
bool intersect(Circle c,Point p){
    return abs(abs(p-c.center)-c.r)<EPS;
}
//線分と線分の交差判定
bool intersect(Segment s,Segment t){
    return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <=0 and ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2)<=0;
}
//線分と円の交差判定，交点の個数を返す
int intersect(Circle c,Segment l){
    Point h=projection(l,c.center);
    //直線まるっと円の外側
    if(norm(h-c.center)-c.r*c.r>EPS)    return 0;
    Real d1=abs(c.center-l.p1),d2=abs(c.center-l.p2);
    //線分が円内
    if(d1<c.r+EPS and d2<c.r+EPS) return 0;
    if((d1<c.r-EPS and d2>c.r+EPS) or (d2<c.r-EPS and d1>c.r+EPS)) return 1;
    //円の外部にまるまるはみ出ていないか
    if(dot(l.p1-h,l.p2-h)<0) return 2;
    return 0;
}
//円と円の位置関係，共通接線の個数を返す
int intersect(Circle c1,Circle c2){
    if(c1.r<c2.r) swap(c1,c2);
    Real d=abs(c1.center-c2.center);
    //2円が離れている
    if(c1.r+c2.r<d)     return 4;
    //2円が外接する
    if(eq(c1.r+c2.r,d)) return 3;
    //2円が交わる
    if(c1.r-c2.r<d)     return 2;
    //円が内接する
    if(eq(c1.r-c2.r,d)) return 1;
    //内包
                        return 0;
}
#line 1 "Geometry/Distance.hpp"
// Distance (Requires: Projection, Intersect)
Real dis(Point a,Point b){
    return abs(a-b);
}
Real dis(Line l,Point p){
    return abs(p-projection(l,p));
}
Real dis(Segment s,Point p){
    Point r=projection(s,p);
    if(intersect(s,r)) return abs(r-p);
    return min(abs(s.p1-p),abs(s.p2-p));
}
Real dis(Segment a,Segment b){
    if(intersect(a,b)) return 0;
    return min({dis(a,b.p1),dis(a,b.p2),dis(b,a.p1),dis(b,a.p2)});
}
Real dis(Polygon a,Polygon b){
    Real ret=-10;
    int n=(int)a.size(),m=(int)b.size();
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){
        Real d=dis(Segment(a[i],a[(i+1)%n]),Segment(b[j],b[(j+1)%m]));
        if(ret<0) ret=d;
        else      ret=min(ret,d);
    }
    return ret;
}
Real dis(Polygon poly,Point p){
    Real ret=-10;
    int n=(int)poly.size();
    for(int i=0;i<n;i++){
        Real d=dis(Segment(poly[i],poly[(i+1)%n]),p);
        if(ret<0) ret=d;
        else      ret=min(ret,d);
    }
    return ret;
}
#line 1 "Geometry/CrossPoint.hpp"
//intersectをチェックすること
//v
Point crosspoint(Line l,Line m){
   Real A=cross(m.p2-m.p1,m.p1-l.p1);
   Real B=cross(m.p2-m.p1,l.p2-l.p1);
   if(eq(A,0) and eq(B,0)) return l.p1;
   if(eq(B,0))             throw "NAI";
   return l.p1+A/B*(l.p2-l.p1);   
}
Point crosspoint(Segment l,Segment m){
   return crosspoint(Line(l),Line(m));
}
vector<Point> crosspoint(Circle c,Line l){
   vector<Point> ret;
   Point h=projection(l,c.center);
   Real d=sqrt(c.r*c.r-norm(h-c.center));
   Point e=(l.p2-l.p1)*(1/abs(l.p2-l.p1));
   if(c.r*c.r+EPS<norm(h-c.center)) return ret;
   if(eq(dis(l,c.center),c.r)){
       ret.push_back(h);
       return ret;
   }
   ret.push_back(h+e*d);ret.push_back(h-e*d);
   return ret;
}
//要verify，
vector<Point> crosspoint(Circle c,Segment s){
   Line l=Line(s.p1,s.p2);
   int ko=intersect(c,s);
   if(ko==2) return crosspoint(c,l);
   vector<Point> ret;
   if(ko==0) return ret;
   ret=crosspoint(c,l);
   if(ret.size()==1) return ret;
   vector<Point> rret;
   //交点で挟める方を返す
   if(dot(s.p1-ret[0],s.p2-ret[0])<0)  rret.push_back(ret[0]);
   else                                rret.push_back(ret[1]);
   return rret;
}
//v
vector<Point> crosspoint(Circle c1,Circle c2){
   vector<Point> ret;
   int isec=intersect(c1,c2);
   if(isec==0 or isec==4) return ret;
   Real d=abs(c1.center-c2.center);
   Real a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
   Real t=atan2(c2.center.imag()-c1.center.imag(),c2.center.real()-c1.center.real());
   ret.push_back(c1.center+Point(cos(t+a)*c1.r,sin(t+a)*c1.r));
   ret.push_back(c1.center+Point(cos(t-a)*c1.r,sin(t-a)*c1.r));
   return ret;
}
#line 1 "Geometry/Angle.hpp"
// angle of a-b-c
Real get_smaller_angle(Point a,Point b,Point c){
    Point v=a-b,w=c-b;
    auto A=atan2(imag(v),real(v));
    auto B=atan2(imag(w),real(w));
    if(A>B) swap(A,B);
    Real res=B-A;
    return min(res,pi*2.0-res);
}
#line 1 "Geometry/InscribedCircle.hpp"
// 内接円
Circle inscribed_circle(Point a,Point b,Point c){
    Real A,B;
    {
        Point t=c-a;
        t*=conj(b-a);
        t/=norm(b-a);
        A=atan2(imag(t),real(t));
    }
    {
        Point t=a-b;
        t*=conj(c-b);
        t/=norm(c-b);
        B=atan2(imag(t),real(t));
    }
    Line Amid=Line(a,a+rotate(A*0.5,b-a)),Bmid=Line(b,b+rotate(B*0.5,c-b));
    auto center=crosspoint(Amid,Bmid);
    auto h=projection(Line(a,b),center);
    return Circle(center,dis(h,center));
}
#line 1 "Geometry/CircumscribedCircle.hpp"
// 外接円
Circle circumscribed_circle(Point a,Point b,Point c){
    Line orth_ab((a+b)*0.5,(a+b)*0.5+Point(-imag(b-a),real(b-a)));
    Line orth_bc((b+c)*0.5,(b+c)*0.5+Point(-imag(c-b),real(c-b)));
    Point center=crosspoint(orth_ab,orth_bc);
    Real r=dis(a,center);
    return Circle(center,r);
}
#line 1 "Geometry/Tangent.hpp"
//v
//点pから引いた円cの接線の接点を返す
vector<Point> tangent(Circle c,Point p){
    return crosspoint(c,Circle(p,sqrt(norm(c.center-p)-c.r*c.r)));
}
//v
//二円の共通接線，Lineの2点は接点を表す
vector<Line> tangent(Circle c1,Circle c2){
    vector<Line> ret;
    if(c1.r<c2.r) swap(c1,c2);
    Real g=norm(c1.center-c2.center);
    if(eq(g,0)) return ret;
    Point u=(c2.center-c1.center)/sqrt(g);
    Point v=rotate(pi*0.5,u);
    for(int s:{-1,1}){
        Real h=(c1.r+s*c2.r)/sqrt(g);
        if(eq(1-h*h,0)){
            ret.push_back(Line(c1.center+u*c1.r,c1.center+(u+v)*c1.r));
        }
        else if(1-h*h>0){
            Point uu=u*h,vv=v*sqrt(1-h*h);
            ret.push_back(Line(c1.center+(uu+vv)*c1.r,c2.center-(uu+vv)*c2.r*s));
            ret.push_back(Line(c1.center+(uu-vv)*c1.r,c2.center-(uu-vv)*c2.r*s));
        }
    }
    return ret;
}
#line 1 "Geometry/Contain.hpp"
// out 0, on 1, in 2
int contains(Polygon poly,Point p){
    int res=0;
    int n=(int)poly.size();
    for(int i=0;i<n;i++){
        Point a=poly[i]-p,b=poly[(i+1)%n]-p;
        if(imag(a)>imag(b)) swap(a,b);
        if(imag(a)<=0 and 0<imag(b) and cross(a,b)<0) res^=1;
        if(eq(cross(a,b),0) and (dot(a,b)<0 or eq(dot(a,b),0))) return 1;
    }
    if(res) res=2;
    return res;
}
#line 1 "Geometry/MinimumBoundingCircle.hpp"
//最小包含円を返す　計算量は期待値O(n)
Circle MinimumBoundingCircle(vector<Point> v){
    int n=v.size();
    //ランダムシャッフル．いぢわるされたくないもんだ
    mt19937 mt(time(0));
    shuffle(v.begin(),v.end(),mt);
    Circle ret(0,0);

    auto make_circle2=[&](Point a,Point b){
        return Circle((a+b)*0.5,dis(a,b)/2);
    };

    auto make_circle3=[&](Point A,Point B,Point C){
        Point cent=circumscribed_circle(A,B,C).center;
        return Circle(cent,dis(cent,A));
    };

    auto isIn=[&](Point a){
        return dis(ret.center,a)<ret.r+EPS;
    };

    ret=make_circle2(v[0],v[1]);
    for(int i=2;i<n;i++){
        //v[i]が円に入っていないなら
        if(!isIn(v[i])){
            //円内にないなら点v[i]は必ず円周上に来る
            ret=make_circle2(v[0],v[i]);
            for(int j=1;j<i;j++){
                if(!isIn(v[j])){
                    //この時iとjが円周上を考える
                    ret=make_circle2(v[i],v[j]);
                    //最後の1点の決定
                    for(int k=0;k<j;k++)if(!isIn(v[k])) ret=make_circle3(v[i],v[j],v[k]);
                }
            }
        }
    }
    return ret;
}
#line 1 "Geometry/ClosestPair.hpp"
// 最近点対
// O(NlogN)
Real closest_pair(vector<Point> ps){
    sort(ALL(ps),[&](Point a,Point b){
        return real(a)<real(b);
    });
    function<Real(int,int)> rec=[&](int l,int r){
        if(r-l<=1) return (Real)1e18;
        int m=(l+r)/2;
        Real x=real(ps[m]);
        Real ret=min(rec(l,m),rec(m,r));
        inplace_merge(begin(ps)+l,begin(ps)+m,begin(ps)+r,[&](Point a,Point b){
            return imag(a)<imag(b);
        });
        // 分割を跨いで最小距離があるか調べる
        vector<Point> b;
        for(int i=l;i<r;i++){
            if(abs(real(ps[i])-x)>=ret) continue;
            for(int j=(int)b.size()-1;j>=0;j--){
                if(abs(imag(ps[i]-b[j]))>=ret) break;
                ret=min(ret,abs(ps[i]-b[j]));
            }
            b.push_back(ps[i]);
        }
        return ret;
    };
    return rec(0,(int)ps.size());
}
#line 1 "Geometry/Convex.hpp"
// 凸多角形系統
// 凸多角形の頂点は反時計周りに訪れる順序
// v
// 頂点は反時計周りに訪れる順序，時計回りとなるような3点があるとfalse
bool is_convex(const vector<Point> &ps){
    int n=(int)ps.size();
    for(int i=0;i<n;i++)if(ccw(ps[(i+n-1)%n],ps[i],ps[(i+1)%n])==-1)return false;
    return true;
}

// 凸包，あんまりよくわかってない．直線状に頂点をのせない場合(↑)，のせる場合(↓)
vector<Point> convex_hull(vector<Point> p){
    int n=(int)p.size(),k=0;
    if(n<=2)return p;
    sort(begin(p),end(p),[](Point a,Point b){
        return real(a)!=real(b)?real(a)<real(b):imag(a)<imag(b);
    });
    vector<Point>ch(2*n);
    for(int i=0;i<n;ch[k++]=p[i++]){
        // while(k>=2 and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<EPS)k--;
        while(k>=2 and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<0)k--;
    }
    for(int i=n-2,t=k+1;i>=0;ch[k++]=p[i--]){
        // while(k>=t and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<EPS)k--;
        while(k>=t and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<0)k--;
    }
    ch.resize(k-1);
    return ch;
}
#line 18 "Geometry/include.hpp"
Back to top page