精华内容
下载资源
问答
  • // `计算几何模板` const double eps = 1e-8; const double inf = 1e20; const double pi = acos(-1.0); const int maxp = 1010; //`Compares a double to zero` int sgn(double x){ if(fabs(x) < eps)re...

    二维几何

    // `计算几何模板`
    const double eps = 1e-8;
    const double inf = 1e20;
    const double pi = acos(-1.0);
    const int maxp = 1010;
    //`Compares a double to zero`
    int sgn(double x){
        if(fabs(x) < eps)return 0;
        if(x < 0)return -1;
        else return 1;
    }
    //square of a double
    inline double sqr(double x){return x*x;}
    /*
     * Point
     * Point()               - Empty constructor
     * Point(double _x,double _y)  - constructor
     * input()             - double input
     * output()            - %.2f output
     * operator ==         - compares x and y
     * operator <          - compares first by x, then by y
     * operator -          - return new Point after subtracting curresponging x and y
     * operator ^          - cross product of 2d points
     * operator *          - dot product
     * len()               - gives length from origin
     * len2()              - gives square of length from origin
     * distance(Point p)   - gives distance from p
     * operator + Point b  - returns new Point after adding curresponging x and y
     * operator * double k - returns new Point after multiplieing x and y by k
     * operator / double k - returns new Point after divideing x and y by k
     * rad(Point a,Point b)- returns the angle of Point a and Point b from this Point
     * trunc(double r)     - return Point that if truncated the distance from center to r
     * rotleft()           - returns 90 degree ccw rotated point
     * rotright()          - returns 90 degree cw rotated point
     * rotate(Point p,double angle) - returns Point after rotateing the Point centering at p by angle radian ccw
     */
    struct Point{
        double x,y;
        Point(){}
        Point(double _x,double _y){
            x = _x;
            y = _y;
        }
        void input(){
            scanf("%lf%lf",&x,&y);
        }
        void output(){
            printf("%.2f %.2f\n",x,y);
        }
        bool operator == (Point b)const{
            return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
        }
        bool operator < (Point b)const{
            return sgn(x-b.x)== 0?sgn(y-b.y)<0:x<b.x;
        }
        Point operator -(const Point &b)const{
            return Point(x-b.x,y-b.y);
        }
        //叉积
        double operator ^(const Point &b)const{
            return x*b.y - y*b.x;
        }
        //点积
        double operator *(const Point &b)const{
            return x*b.x + y*b.y;
        }
        //返回长度
        double len(){
            return hypot(x,y);//库函数
        }
        //返回长度的平方
        double len2(){
            return x*x + y*y;
        }
        //返回两点的距离
        double distance(Point p){
            return hypot(x-p.x,y-p.y);
        }
        Point operator +(const Point &b)const{
            return Point(x+b.x,y+b.y);
        }
        Point operator *(const double &k)const{
            return Point(x*k,y*k);
        }
        Point operator /(const double &k)const{
            return Point(x/k,y/k);
        }
        //`计算pa  和  pb 的夹角`
        //`就是求这个点看a,b 所成的夹角`
        //`测试 LightOJ1203`
        double rad(Point a,Point b){
            Point p = *this;
            return fabs(atan2( fabs((a-p)^(b-p)),(a-p)*(b-p) ));
        }
        //`化为长度为r的向量`
        Point trunc(double r){
            double l = len();
            if(!sgn(l))return *this;
            r /= l;
            return Point(x*r,y*r);
        }
        //`逆时针旋转90度`
        Point rotleft(){
            return Point(-y,x);
        }
        //`顺时针旋转90度`
        Point rotright(){
            return Point(y,-x);
        }
        //`绕着p点逆时针旋转angle`
        Point rotate(Point p,double angle){
            Point v = (*this) - p;
            double c = cos(angle), s = sin(angle);
            return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c);
        }
    };
    /*
     * Stores two points
     * Line()                         - Empty constructor
     * Line(Point _s,Point _e)        - Line through _s and _e
     * operator ==                    - checks if two points are same
     * Line(Point p,double angle)     - one end p , another end at angle degree
     * Line(double a,double b,double c) - Line of equation ax + by + c = 0
     * input()                        - inputs s and e
     * adjust()                       - orders in such a way that s < e
     * length()                       - distance of se
     * angle()                        - return 0 <= angle < pi
     * relation(Point p)              - 3 if point is on line
     *                                  1 if point on the left of line
     *                                  2 if point on the right of line
     * pointonseg(double p)           - return true if point on segment
     * parallel(Line v)               - return true if they are parallel
     * segcrossseg(Line v)            - returns 0 if does not intersect
     *                                  returns 1 if non-standard intersection
     *                                  returns 2 if intersects
     * linecrossseg(Line v)           - line and seg
     * linecrossline(Line v)          - 0 if parallel
     *                                  1 if coincides
     *                                  2 if intersects
     * crosspoint(Line v)             - returns intersection point
     * dispointtoline(Point p)        - distance from point p to the line
     * dispointtoseg(Point p)         - distance from p to the segment
     * dissegtoseg(Line v)            - distance of two segment
     * lineprog(Point p)              - returns projected point p on se line
     * symmetrypoint(Point p)         - returns reflection point of p over se
     *
     */
    struct Line{
        Point s,e;
        Line(){}
        Line(Point _s,Point _e){
            s = _s;
            e = _e;
        }
        bool operator ==(Line v){
            return (s == v.s)&&(e == v.e);
        }
        //`根据一个点和倾斜角angle确定直线,0<=angle<pi`
        Line(Point p,double angle){
            s = p;
            if(sgn(angle-pi/2) == 0){
                e = (s + Point(0,1));
            }
            else{
                e = (s + Point(1,tan(angle)));
            }
        }
        //ax+by+c=0
        Line(double a,double b,double c){
            if(sgn(a) == 0){
                s = Point(0,-c/b);
                e = Point(1,-c/b);
            }
            else if(sgn(b) == 0){
                s = Point(-c/a,0);
                e = Point(-c/a,1);
            }
            else{
                s = Point(0,-c/b);
                e = Point(1,(-c-a)/b);
            }
        }
        void input(){
            s.input();
            e.input();
        }
        void adjust(){
            if(e < s)swap(s,e);
        }
        //求线段长度
        double length(){
            return s.distance(e);
        }
        //`返回直线倾斜角 0<=angle<pi`
        double angle(){
            double k = atan2(e.y-s.y,e.x-s.x);
            if(sgn(k) < 0)k += pi;
            if(sgn(k-pi) == 0)k -= pi;
            return k;
        }
        //`点和直线关系`
        //`1  在左侧`
        //`2  在右侧`
        //`3  在直线上`
        int relation(Point p){
            int c = sgn((p-s)^(e-s));
            if(c < 0)return 1;
            else if(c > 0)return 2;
            else return 3;
        }
        // 点在线段上的判断
        bool pointonseg(Point p){
            return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;
        }
        //`两向量平行(对应直线平行或重合)`
        bool parallel(Line v){
            return sgn((e-s)^(v.e-v.s)) == 0;
        }
        //`两线段相交判断`
        //`2 规范相交`
        //`1 非规范相交`
        //`0 不相交`
        int segcrossseg(Line v){
            int d1 = sgn((e-s)^(v.s-s));
            int d2 = sgn((e-s)^(v.e-s));
            int d3 = sgn((v.e-v.s)^(s-v.s));
            int d4 = sgn((v.e-v.s)^(e-v.s));
            if( (d1^d2)==-2 && (d3^d4)==-2 )return 2;
            return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||
                (d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||
                (d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||
                (d4==0 && sgn((e-v.s)*(e-v.e))<=0);
        }
        //`直线和线段相交判断`
        //`-*this line   -v seg`
        //`2 规范相交`
        //`1 非规范相交`
        //`0 不相交`
        int linecrossseg(Line v){
            int d1 = sgn((e-s)^(v.s-s));
            int d2 = sgn((e-s)^(v.e-s));
            if((d1^d2)==-2) return 2;
            return (d1==0||d2==0);
        }
        //`两直线关系`
        //`0 平行`
        //`1 重合`
        //`2 相交`
        int linecrossline(Line v){
            if((*this).parallel(v))
                return v.relation(s)==3;
            return 2;
        }
        //`求两直线的交点`
        //`要保证两直线不平行或重合`
        Point crosspoint(Line v){
            double a1 = (v.e-v.s)^(s-v.s);
            double a2 = (v.e-v.s)^(e-v.s);
            return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
        }
        //点到直线的距离
        double dispointtoline(Point p){
            return fabs((p-s)^(e-s))/length();
        }
        //点到线段的距离
        double dispointtoseg(Point p){
            if(sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0)
                return min(p.distance(s),p.distance(e));
            return dispointtoline(p);
        }
        //`返回线段到线段的距离`
        //`前提是两线段不相交,相交距离就是0了`
        double dissegtoseg(Line v){
            return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));
        }
        //`返回点p在直线上的投影`
        Point lineprog(Point p){
            return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
        }
        //`返回点p关于直线的对称点`
        Point symmetrypoint(Point p){
            Point q = lineprog(p);
            return Point(2*q.x-p.x,2*q.y-p.y);
        }
    };
    //圆
    struct circle{
        Point p;//圆心
        double r;//半径
        circle(){}
        circle(Point _p,double _r){
            p = _p;
            r = _r;
        }
        circle(double x,double y,double _r){
            p = Point(x,y);
            r = _r;
        }
        //`三角形的外接圆`
        //`需要Point的+ /  rotate()  以及Line的crosspoint()`
        //`利用两条边的中垂线得到圆心`
        //`测试:UVA12304`
        circle(Point a,Point b,Point c){
            Line u = Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
            Line v = Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
            p = u.crosspoint(v);
            r = p.distance(a);
        }
        //`三角形的内切圆`
        //`参数bool t没有作用,只是为了和上面外接圆函数区别`
        //`测试:UVA12304`
        circle(Point a,Point b,Point c,bool t){
            Line u,v;
            double m = atan2(b.y-a.y,b.x-a.x), n = atan2(c.y-a.y,c.x-a.x);
            u.s = a;
            u.e = u.s + Point(cos((n+m)/2),sin((n+m)/2));
            v.s = b;
            m = atan2(a.y-b.y,a.x-b.x) , n = atan2(c.y-b.y,c.x-b.x);
            v.e = v.s + Point(cos((n+m)/2),sin((n+m)/2));
            p = u.crosspoint(v);
            r = Line(a,b).dispointtoseg(p);
        }
        //输入
        void input(){
            p.input();
            scanf("%lf",&r);
        }
        //输出
        void output(){
            printf("%.2lf %.2lf %.2lf\n",p.x,p.y,r);
        }
        bool operator == (circle v){
            return (p==v.p) && sgn(r-v.r)==0;
        }
        bool operator < (circle v)const{
            return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));
        }
        //面积
        double area(){
            return pi*r*r;
        }
        //周长
        double circumference(){
            return 2*pi*r;
        }
        //`点和圆的关系`
        //`0 圆外`
        //`1 圆上`
        //`2 圆内`
        int relation(Point b){
            double dst = b.distance(p);
            if(sgn(dst-r) < 0)return 2;
            else if(sgn(dst-r)==0)return 1;
            return 0;
        }
        //`线段和圆的关系`
        //`比较的是圆心到线段的距离和半径的关系`
        int relationseg(Line v){
            double dst = v.dispointtoseg(p);
            if(sgn(dst-r) < 0)return 2;
            else if(sgn(dst-r) == 0)return 1;
            return 0;
        }
        //`直线和圆的关系`
        //`比较的是圆心到直线的距离和半径的关系`
        int relationline(Line v){
            double dst = v.dispointtoline(p);
            if(sgn(dst-r) < 0)return 2;
            else if(sgn(dst-r) == 0)return 1;
            return 0;
        }
        //`两圆的关系`
        //`5 相离`
        //`4 外切`
        //`3 相交`
        //`2 内切`
        //`1 内含`
        //`需要Point的distance`
        //`测试:UVA12304`
        int relationcircle(circle v){
            double d = p.distance(v.p);
            if(sgn(d-r-v.r) > 0)return 5;
            if(sgn(d-r-v.r) == 0)return 4;
            double l = fabs(r-v.r);
            if(sgn(d-r-v.r)<0 && sgn(d-l)>0)return 3;
            if(sgn(d-l)==0)return 2;
            if(sgn(d-l)<0)return 1;
        }
        //`求两个圆的交点,返回0表示没有交点,返回1是一个交点,2是两个交点`
        //`需要relationcircle`
        //`测试:UVA12304`
        int pointcrosscircle(circle v,Point &p1,Point &p2){
            int rel = relationcircle(v);
            if(rel == 1 || rel == 5)return 0;
            double d = p.distance(v.p);
            double l = (d*d+r*r-v.r*v.r)/(2*d);
            double h = sqrt(r*r-l*l);
            Point tmp = p + (v.p-p).trunc(l);
            p1 = tmp + ((v.p-p).rotleft().trunc(h));
            p2 = tmp + ((v.p-p).rotright().trunc(h));
            if(rel == 2 || rel == 4)
                return 1;
            return 2;
        }
        //`求直线和圆的交点,返回交点个数`
        int pointcrossline(Line v,Point &p1,Point &p2){
            if(!(*this).relationline(v))return 0;
            Point a = v.lineprog(p);
            double d = v.dispointtoline(p);
            d = sqrt(r*r-d*d);
            if(sgn(d) == 0){
                p1 = a;
                p2 = a;
                return 1;
            }
            p1 = a + (v.e-v.s).trunc(d);
            p2 = a - (v.e-v.s).trunc(d);
            return 2;
        }
        //`得到过a,b两点,半径为r1的两个圆`
        int gercircle(Point a,Point b,double r1,circle &c1,circle &c2){
            circle x(a,r1),y(b,r1);
            int t = x.pointcrosscircle(y,c1.p,c2.p);
            if(!t)return 0;
            c1.r = c2.r = r;
            return t;
        }
        //`得到与直线u相切,过点q,半径为r1的圆`
        //`测试:UVA12304`
        int getcircle(Line u,Point q,double r1,circle &c1,circle &c2){
            double dis = u.dispointtoline(q);
            if(sgn(dis-r1*2)>0)return 0;
            if(sgn(dis) == 0){
                c1.p = q + ((u.e-u.s).rotleft().trunc(r1));
                c2.p = q + ((u.e-u.s).rotright().trunc(r1));
                c1.r = c2.r = r1;
                return 2;
            }
            Line u1 = Line((u.s + (u.e-u.s).rotleft().trunc(r1)),(u.e + (u.e-u.s).rotleft().trunc(r1)));
            Line u2 = Line((u.s + (u.e-u.s).rotright().trunc(r1)),(u.e + (u.e-u.s).rotright().trunc(r1)));
            circle cc = circle(q,r1);
            Point p1,p2;
            if(!cc.pointcrossline(u1,p1,p2))cc.pointcrossline(u2,p1,p2);
            c1 = circle(p1,r1);
            if(p1 == p2){
                c2 = c1;
                return 1;
            }
            c2 = circle(p2,r1);
            return 2;
        }
        //`同时与直线u,v相切,半径为r1的圆`
        //`测试:UVA12304`
        int getcircle(Line u,Line v,double r1,circle &c1,circle &c2,circle &c3,circle &c4){
            if(u.parallel(v))return 0;//两直线平行
            Line u1 = Line(u.s + (u.e-u.s).rotleft().trunc(r1),u.e + (u.e-u.s).rotleft().trunc(r1));
            Line u2 = Line(u.s + (u.e-u.s).rotright().trunc(r1),u.e + (u.e-u.s).rotright().trunc(r1));
            Line v1 = Line(v.s + (v.e-v.s).rotleft().trunc(r1),v.e + (v.e-v.s).rotleft().trunc(r1));
            Line v2 = Line(v.s + (v.e-v.s).rotright().trunc(r1),v.e + (v.e-v.s).rotright().trunc(r1));
            c1.r = c2.r = c3.r = c4.r = r1;
            c1.p = u1.crosspoint(v1);
            c2.p = u1.crosspoint(v2);
            c3.p = u2.crosspoint(v1);
            c4.p = u2.crosspoint(v2);
            return 4;
        }
        //`同时与不相交圆cx,cy相切,半径为r1的圆`
        //`测试:UVA12304`
        int getcircle(circle cx,circle cy,double r1,circle &c1,circle &c2){
            circle x(cx.p,r1+cx.r),y(cy.p,r1+cy.r);
            int t = x.pointcrosscircle(y,c1.p,c2.p);
            if(!t)return 0;
            c1.r = c2.r = r1;
            return t;
        }
    
        //`过一点作圆的切线(先判断点和圆的关系)`
        //`测试:UVA12304`
        int tangentline(Point q,Line &u,Line &v){
            int x = relation(q);
            if(x == 2)return 0;
            if(x == 1){
                u = Line(q,q + (q-p).rotleft());
                v = u;
                return 1;
            }
            double d = p.distance(q);
            double l = r*r/d;
            double h = sqrt(r*r-l*l);
            u = Line(q,p + ((q-p).trunc(l) + (q-p).rotleft().trunc(h)));
            v = Line(q,p + ((q-p).trunc(l) + (q-p).rotright().trunc(h)));
            return 2;
        }
        //`求两圆相交的面积`
        double areacircle(circle v){
            int rel = relationcircle(v);
            if(rel >= 4)return 0.0;
            if(rel <= 2)return min(area(),v.area());
            double d = p.distance(v.p);
            double hf = (r+v.r+d)/2.0;
            double ss = 2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
            double a1 = acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
            a1 = a1*r*r;
            double a2 = acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
            a2 = a2*v.r*v.r;
            return a1+a2-ss;
        }
        //`求圆和三角形pab的相交面积`
        //`测试:POJ3675 HDU3982 HDU2892`
        double areatriangle(Point a,Point b){
            if(sgn((p-a)^(p-b)) == 0)return 0.0;
            Point q[5];
            int len = 0;
            q[len++] = a;
            Line l(a,b);
            Point p1,p2;
            if(pointcrossline(l,q[1],q[2])==2){
                if(sgn((a-q[1])*(b-q[1]))<0)q[len++] = q[1];
                if(sgn((a-q[2])*(b-q[2]))<0)q[len++] = q[2];
            }
            q[len++] = b;
            if(len == 4 && sgn((q[0]-q[1])*(q[2]-q[1]))>0)swap(q[1],q[2]);
            double res = 0;
            for(int i = 0;i < len-1;i++){
                if(relation(q[i])==0||relation(q[i+1])==0){
                    double arg = p.rad(q[i],q[i+1]);
                    res += r*r*arg/2.0;
                }
                else{
                    res += fabs((q[i]-p)^(q[i+1]-p))/2.0;
                }
            }
            return res;
        }
    };
    
    /*
     * n,p  Line l for each side
     * input(int _n)                        - inputs _n size polygon
     * add(Point q)                         - adds a point at end of the list
     * getline()                            - populates line array
     * cmp                                  - comparision in convex_hull order
     * norm()                               - sorting in convex_hull order
     * getconvex(polygon &convex)           - returns convex hull in convex
     * Graham(polygon &convex)              - returns convex hull in convex
     * isconvex()                           - checks if convex
     * relationpoint(Point q)               - returns 3 if q is a vertex
     *                                                2 if on a side
     *                                                1 if inside
     *                                                0 if outside
     * convexcut(Line u,polygon &po)        - left side of u in po
     * gercircumference()                   - returns side length
     * getarea()                            - returns area
     * getdir()                             - returns 0 for cw, 1 for ccw
     * getbarycentre()                      - returns barycenter
     *
     */
    struct polygon{
        int n;
        Point p[maxp];
        Line l[maxp];
        void input(int _n){
            n = _n;
            for(int i = 0;i < n;i++)
                p[i].input();
        }
        void add(Point q){
            p[n++] = q;
        }
        void getline(){
            for(int i = 0;i < n;i++){
                l[i] = Line(p[i],p[(i+1)%n]);
            }
        }
        struct cmp{
            Point p;
            cmp(const Point &p0){p = p0;}
            bool operator()(const Point &aa,const Point &bb){
                Point a = aa, b = bb;
                int d = sgn((a-p)^(b-p));
                if(d == 0){
                    return sgn(a.distance(p)-b.distance(p)) < 0;
                }
                return d > 0;
            }
        };
        //`进行极角排序`
        //`首先需要找到最左下角的点`
        //`需要重载号好Point的 < 操作符(min函数要用) `
        void norm(){
            Point mi = p[0];
            for(int i = 1;i < n;i++)mi = min(mi,p[i]);
            sort(p,p+n,cmp(mi));
        }
        //`得到凸包`
        //`得到的凸包里面的点编号是0$\sim$n-1的`
        //`两种凸包的方法`
        //`注意如果有影响,要特判下所有点共点,或者共线的特殊情况`
        //`测试 LightOJ1203  LightOJ1239`
        void getconvex(polygon &convex){
            sort(p,p+n);
            convex.n = n;
            for(int i = 0;i < min(n,2);i++){
                convex.p[i] = p[i];
            }
            if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
            if(n <= 2)return;
            int &top = convex.n;
            top = 1;
            for(int i = 2;i < n;i++){
                while(top && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)
                    top--;
                convex.p[++top] = p[i];
            }
            int temp = top;
            convex.p[++top] = p[n-2];
            for(int i = n-3;i >= 0;i--){
                while(top != temp && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)
                    top--;
                convex.p[++top] = p[i];
            }
            if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
            convex.norm();//`原来得到的是顺时针的点,排序后逆时针`
        }
        //`得到凸包的另外一种方法`
        //`测试 LightOJ1203  LightOJ1239`
        void Graham(polygon &convex){
            norm();
            int &top = convex.n;
            top = 0;
            if(n == 1){
                top = 1;
                convex.p[0] = p[0];
                return;
            }
            if(n == 2){
                top = 2;
                convex.p[0] = p[0];
                convex.p[1] = p[1];
                if(convex.p[0] == convex.p[1])top--;
                return;
            }
            convex.p[0] = p[0];
            convex.p[1] = p[1];
            top = 2;
            for(int i = 2;i < n;i++){
                while( top > 1 && sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2])) <= 0 )
                    top--;
                convex.p[top++] = p[i];
            }
            if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
        }
        //`判断是不是凸的`
        bool isconvex(){
            bool s[2];
            memset(s,false,sizeof(s));
            for(int i = 0;i < n;i++){
                int j = (i+1)%n;
                int k = (j+1)%n;
                s[sgn((p[j]-p[i])^(p[k]-p[i]))+1] = true;
                if(s[0] && s[2])return false;
            }
            return true;
        }
        //`判断点和任意多边形的关系`
        //` 3 点上`
        //` 2 边上`
        //` 1 内部`
        //` 0 外部`
        int relationpoint(Point q){
            for(int i = 0;i < n;i++){
                if(p[i] == q)return 3;
            }
            getline();
            for(int i = 0;i < n;i++){
                if(l[i].pointonseg(q))return 2;
            }
            int cnt = 0;
            for(int i = 0;i < n;i++){
                int j = (i+1)%n;
                int k = sgn((q-p[j])^(p[i]-p[j]));
                int u = sgn(p[i].y-q.y);
                int v = sgn(p[j].y-q.y);
                if(k > 0 && u < 0 && v >= 0)cnt++;
                if(k < 0 && v < 0 && u >= 0)cnt--;
            }
            return cnt != 0;
        }
        //`直线u切割凸多边形左侧`
        //`注意直线方向`
        //`测试:HDU3982`
        void convexcut(Line u,polygon &po){
            int &top = po.n;//注意引用
            top = 0;
            for(int i = 0;i < n;i++){
                int d1 = sgn((u.e-u.s)^(p[i]-u.s));
                int d2 = sgn((u.e-u.s)^(p[(i+1)%n]-u.s));
                if(d1 >= 0)po.p[top++] = p[i];
                if(d1*d2 < 0)po.p[top++] = u.crosspoint(Line(p[i],p[(i+1)%n]));
            }
        }
        //`得到周长`
        //`测试 LightOJ1239`
        double getcircumference(){
            double sum = 0;
            for(int i = 0;i < n;i++){
                sum += p[i].distance(p[(i+1)%n]);
            }
            return sum;
        }
        //`得到面积`
        double getarea(){
            double sum = 0;
            for(int i = 0;i < n;i++){
                sum += (p[i]^p[(i+1)%n]);
            }
            return fabs(sum)/2;
        }
        //`得到方向`
        //` 1 表示逆时针,0表示顺时针`
        bool getdir(){
            double sum = 0;
            for(int i = 0;i < n;i++)
                sum += (p[i]^p[(i+1)%n]);
            if(sgn(sum) > 0)return 1;
            return 0;
        }
        //`得到重心`
        Point getbarycentre(){
            Point ret(0,0);
            double area = 0;
            for(int i = 1;i < n-1;i++){
                double tmp = (p[i]-p[0])^(p[i+1]-p[0]);
                if(sgn(tmp) == 0)continue;
                area += tmp;
                ret.x += (p[0].x+p[i].x+p[i+1].x)/3*tmp;
                ret.y += (p[0].y+p[i].y+p[i+1].y)/3*tmp;
            }
            if(sgn(area)) ret = ret/area;
            return ret;
        }
        //`多边形和圆交的面积`
        //`测试:POJ3675 HDU3982 HDU2892`
        double areacircle(circle c){
            double ans = 0;
            for(int i = 0;i < n;i++){
                int j = (i+1)%n;
                if(sgn( (p[j]-c.p)^(p[i]-c.p) ) >= 0)
                    ans += c.areatriangle(p[i],p[j]);
                else ans -= c.areatriangle(p[i],p[j]);
            }
            return fabs(ans);
        }
        //`多边形和圆关系`
        //` 2 圆完全在多边形内`
        //` 1 圆在多边形里面,碰到了多边形边界`
        //` 0 其它`
        int relationcircle(circle c){
            getline();
            int x = 2;
            if(relationpoint(c.p) != 1)return 0;//圆心不在内部
            for(int i = 0;i < n;i++){
                if(c.relationseg(l[i])==2)return 0;
                if(c.relationseg(l[i])==1)x = 1;
            }
            return x;
        }
    };
    //`AB X AC`
    double cross(Point A,Point B,Point C){
        return (B-A)^(C-A);
    }
    //`AB*AC`
    double dot(Point A,Point B,Point C){
        return (B-A)*(C-A);
    }
    //`最小矩形面积覆盖`
    //` A 必须是凸包(而且是逆时针顺序)`
    //` 测试 UVA 10173`
    double minRectangleCover(polygon A){
        //`要特判A.n < 3的情况`
        if(A.n < 3)return 0.0;
        A.p[A.n] = A.p[0];
        double ans = -1;
        int r = 1, p = 1, q;
        for(int i = 0;i < A.n;i++){
            //`卡出离边A.p[i] - A.p[i+1]最远的点`
            while( sgn( cross(A.p[i],A.p[i+1],A.p[r+1]) - cross(A.p[i],A.p[i+1],A.p[r]) ) >= 0 )
                r = (r+1)%A.n;
            //`卡出A.p[i] - A.p[i+1]方向上正向n最远的点`
            while(sgn( dot(A.p[i],A.p[i+1],A.p[p+1]) - dot(A.p[i],A.p[i+1],A.p[p]) ) >= 0 )
                p = (p+1)%A.n;
            if(i == 0)q = p;
            //`卡出A.p[i] - A.p[i+1]方向上负向最远的点`
            while(sgn(dot(A.p[i],A.p[i+1],A.p[q+1]) - dot(A.p[i],A.p[i+1],A.p[q])) <= 0)
                q = (q+1)%A.n;
            double d = (A.p[i] - A.p[i+1]).len2();
            double tmp = cross(A.p[i],A.p[i+1],A.p[r]) *
                (dot(A.p[i],A.p[i+1],A.p[p]) - dot(A.p[i],A.p[i+1],A.p[q]))/d;
            if(ans < 0 || ans > tmp)ans = tmp;
        }
        return ans;
    }
    
    //`直线切凸多边形`
    //`多边形是逆时针的,在q1q2的左侧`
    //`测试:HDU3982`
    vector<Point> convexCut(const vector<Point> &ps,Point q1,Point q2){
        vector<Point>qs;
        int n = ps.size();
        for(int i = 0;i < n;i++){
            Point p1 = ps[i], p2 = ps[(i+1)%n];
            int d1 = sgn((q2-q1)^(p1-q1)), d2 = sgn((q2-q1)^(p2-q1));
            if(d1 >= 0)
                qs.push_back(p1);
            if(d1 * d2 < 0)
                qs.push_back(Line(p1,p2).crosspoint(Line(q1,q2)));
        }
        return qs;
    }
    //`半平面交`
    //`测试 POJ3335 POJ1474 POJ1279`
    //***************************
    struct halfplane:public Line{
        double angle;
        halfplane(){}
        //`表示向量s->e逆时针(左侧)的半平面`
        halfplane(Point _s,Point _e){
            s = _s;
            e = _e;
        }
        halfplane(Line v){
            s = v.s;
            e = v.e;
        }
        void calcangle(){
            angle = atan2(e.y-s.y,e.x-s.x);
        }
        bool operator <(const halfplane &b)const{
            return angle < b.angle;
        }
    };
    struct halfplanes{
        int n;
        halfplane hp[maxp];
        Point p[maxp];
        int que[maxp];
        int st,ed;
        void push(halfplane tmp){
            hp[n++] = tmp;
        }
        //去重
        void unique(){
            int m = 1;
            for(int i = 1;i < n;i++){
                if(sgn(hp[i].angle-hp[i-1].angle) != 0)
                    hp[m++] = hp[i];
                else if(sgn( (hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s) ) > 0)
                    hp[m-1] = hp[i];
            }
            n = m;
        }
        bool halfplaneinsert(){
            for(int i = 0;i < n;i++)hp[i].calcangle();
            sort(hp,hp+n);
            unique();
            que[st=0] = 0;
            que[ed=1] = 1;
            p[1] = hp[0].crosspoint(hp[1]);
            for(int i = 2;i < n;i++){
                while(st<ed && sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0)ed--;
                while(st<ed && sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0)st++;
                que[++ed] = i;
                if(hp[i].parallel(hp[que[ed-1]]))return false;
                p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
            }
            while(st<ed && sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0)ed--;
            while(st<ed && sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0)st++;
            if(st+1>=ed)return false;
            return true;
        }
        //`得到最后半平面交得到的凸多边形`
        //`需要先调用halfplaneinsert() 且返回true`
        void getconvex(polygon &con){
            p[st] = hp[que[st]].crosspoint(hp[que[ed]]);
            con.n = ed-st+1;
            for(int j = st,i = 0;j <= ed;i++,j++)
                con.p[i] = p[j];
        }
    };
    //***************************
    
    const int maxn = 1010;
    struct circles{
        circle c[maxn];
        double ans[maxn];//`ans[i]表示被覆盖了i次的面积`
        double pre[maxn];
        int n;
        circles(){}
        void add(circle cc){
            c[n++] = cc;
        }
        //`x包含在y中`
        bool inner(circle x,circle y){
            if(x.relationcircle(y) != 1)return 0;
            return sgn(x.r-y.r)<=0?1:0;
        }
        //圆的面积并去掉内含的圆
        void init_or(){
            bool mark[maxn] = {0};
            int i,j,k=0;
            for(i = 0;i < n;i++){
                for(j = 0;j < n;j++)
                    if(i != j && !mark[j]){
                        if( (c[i]==c[j])||inner(c[i],c[j]) )break;
                    }
                if(j < n)mark[i] = 1;
            }
            for(i = 0;i < n;i++)
                if(!mark[i])
                    c[k++] = c[i];
            n = k;
        }
        //`圆的面积交去掉内含的圆`
        void init_add(){
            int i,j,k;
            bool mark[maxn] = {0};
            for(i = 0;i < n;i++){
                for(j = 0;j < n;j++)
                    if(i != j && !mark[j]){
                        if( (c[i]==c[j])||inner(c[j],c[i]) )break;
                    }
                if(j < n)mark[i] = 1;
            }
            for(i = 0;i < n;i++)
                if(!mark[i])
                    c[k++] = c[i];
            n = k;
        }
        //`半径为r的圆,弧度为th对应的弓形的面积`
        double areaarc(double th,double r){
            return 0.5*r*r*(th-sin(th));
        }
        //`测试SPOJVCIRCLES SPOJCIRUT`
        //`SPOJVCIRCLES求n个圆并的面积,需要加上init\_or()去掉重复圆(否则WA)`
        //`SPOJCIRUT 是求被覆盖k次的面积,不能加init\_or()`
        //`对于求覆盖多少次面积的问题,不能解决相同圆,而且不能init\_or()`
        //`求多圆面积并,需要init\_or,其中一个目的就是去掉相同圆`
        void getarea(){
            memset(ans,0,sizeof(ans));
            vector<pair<double,int> >v;
            for(int i = 0;i < n;i++){
                v.clear();
                v.push_back(make_pair(-pi,1));
                v.push_back(make_pair(pi,-1));
                for(int j = 0;j < n;j++)
                    if(i != j){
                        Point q = (c[j].p - c[i].p);
                        double ab = q.len(),ac = c[i].r, bc = c[j].r;
                        if(sgn(ab+ac-bc)<=0){
                            v.push_back(make_pair(-pi,1));
                            v.push_back(make_pair(pi,-1));
                            continue;
                        }
                        if(sgn(ab+bc-ac)<=0)continue;
                        if(sgn(ab-ac-bc)>0)continue;
                        double th = atan2(q.y,q.x), fai = acos((ac*ac+ab*ab-bc*bc)/(2.0*ac*ab));
                        double a0 = th-fai;
                        if(sgn(a0+pi)<0)a0+=2*pi;
                        double a1 = th+fai;
                        if(sgn(a1-pi)>0)a1-=2*pi;
                        if(sgn(a0-a1)>0){
                            v.push_back(make_pair(a0,1));
                            v.push_back(make_pair(pi,-1));
                            v.push_back(make_pair(-pi,1));
                            v.push_back(make_pair(a1,-1));
                        }
                        else{
                            v.push_back(make_pair(a0,1));
                            v.push_back(make_pair(a1,-1));
                        }
                    }
                sort(v.begin(),v.end());
                int cur = 0;
                for(int j = 0;j < v.size();j++){
                    if(cur && sgn(v[j].first-pre[cur])){
                        ans[cur] += areaarc(v[j].first-pre[cur],c[i].r);
                        ans[cur] += 0.5*(Point(c[i].p.x+c[i].r*cos(pre[cur]),c[i].p.y+c[i].r*sin(pre[cur]))^Point(c[i].p.x+c[i].r*cos(v[j].first),c[i].p.y+c[i].r*sin(v[j].first)));
                    }
                    cur += v[j].second;
                    pre[cur] = v[j].first;
                }
            }
            for(int i = 1;i < n;i++)
                ans[i] -= ans[i+1];
        }
    };

    三维几何

    const double eps = 1e-8;
    int sgn(double x){
        if(fabs(x) < eps)return 0;
        if(x < 0)return -1;
        else return 1;
    }
    struct Point3{
        double x,y,z;
        Point3(double _x = 0,double _y = 0,double _z = 0){
            x = _x;
            y = _y;
            z = _z;
        }
        void input(){
            scanf("%lf%lf%lf",&x,&y,&z);
        }
        void output(){
            scanf("%.2lf %.2lf %.2lf\n",x,y,z);
        }
        bool operator ==(const Point3 &b)const{
            return sgn(x-b.x) == 0 && sgn(y-b.y) == 0 && sgn(z-b.z) == 0;
        }
        bool operator <(const Point3 &b)const{
            return sgn(x-b.x)==0?(sgn(y-b.y)==0?sgn(z-b.z)<0:y<b.y):x<b.x;
        }
        double len(){
            return sqrt(x*x+y*y+z*z);
        }
        double len2(){
            return x*x+y*y+z*z;
        }
        double distance(const Point3 &b)const{
            return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
        }
        Point3 operator -(const Point3 &b)const{
            return Point3(x-b.x,y-b.y,z-b.z);
        }
        Point3 operator +(const Point3 &b)const{
            return Point3(x+b.x,y+b.y,z+b.z);
        }
        Point3 operator *(const double &k)const{
            return Point3(x*k,y*k,z*k);
        }
        Point3 operator /(const double &k)const{
            return Point3(x/k,y/k,z/k);
        }
        //点乘
        double operator *(const Point3 &b)const{
            return x*b.x+y*b.y+z*b.z;
        }
        //叉乘
        Point3 operator ^(const Point3 &b)const{
            return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
        }
        double rad(Point3 a,Point3 b){
            Point3 p = (*this);
            return acos( ( (a-p)*(b-p) )/ (a.distance(p)*b.distance(p)) );
        }
        //变换长度
        Point3 trunc(double r){
            double l = len();
            if(!sgn(l))return *this;
            r /= l;
            return Point3(x*r,y*r,z*r);
        }
    };
    struct Line3
    {
        Point3 s,e;
        Line3(){}
        Line3(Point3 _s,Point3 _e)
        {
            s = _s;
            e = _e;
        }
        bool operator ==(const Line3 v)
        {
            return (s==v.s)&&(e==v.e);
        }
        void input()
        {
            s.input();
            e.input();
        }
        double length()
        {
            return s.distance(e);
        }
        //点到直线距离
        double dispointtoline(Point3 p)
        {
            return ((e-s)^(p-s)).len()/s.distance(e);
        }
        //点到线段距离
        double dispointtoseg(Point3 p)
        {
            if(sgn((p-s)*(e-s)) < 0 || sgn((p-e)*(s-e)) < 0)
                return min(p.distance(s),e.distance(p));
            return dispointtoline(p);
        }
        //`返回点p在直线上的投影`
        Point3 lineprog(Point3 p)
        {
            return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
        }
        //`p绕此向量逆时针arg角度`
        Point3 rotate(Point3 p,double ang)
        {
            if(sgn(((s-p)^(e-p)).len()) == 0)return p;
            Point3 f1 = (e-s)^(p-s);
            Point3 f2 = (e-s)^(f1);
            double len = ((s-p)^(e-p)).len()/s.distance(e);
            f1 = f1.trunc(len); f2 = f2.trunc(len);
            Point3 h = p+f2;
            Point3 pp = h+f1;
            return h + ((p-h)*cos(ang)) + ((pp-h)*sin(ang));
        }
        //`点在直线上`
        bool pointonseg(Point3 p)
        {
            return sgn( ((s-p)^(e-p)).len() ) == 0 && sgn((s-p)*(e-p)) == 0;
        }
    };
    struct Plane
    {
        Point3 a,b,c,o;//`平面上的三个点,以及法向量`
        Plane(){}
        Plane(Point3 _a,Point3 _b,Point3 _c)
        {
            a = _a;
            b = _b;
            c = _c;
            o = pvec();
        }
        Point3 pvec()
        {
            return (b-a)^(c-a);
        }
        //`ax+by+cz+d = 0`
        Plane(double _a,double _b,double _c,double _d)
        {
            o = Point3(_a,_b,_c);
            if(sgn(_a) != 0)
                a = Point3((-_d-_c-_b)/_a,1,1);
            else if(sgn(_b) != 0)
                a = Point3(1,(-_d-_c-_a)/_b,1);
            else if(sgn(_c) != 0)
                a = Point3(1,1,(-_d-_a-_b)/_c);
        }
        //`点在平面上的判断`
        bool pointonplane(Point3 p)
        {
            return sgn((p-a)*o) == 0;
        }
        //`两平面夹角`
        double angleplane(Plane f)
        {
            return acos(o*f.o)/(o.len()*f.o.len());
        }
        //`平面和直线的交点,返回值是交点个数`
        int crossline(Line3 u,Point3 &p)
        {
            double x = o*(u.e-a);
            double y = o*(u.s-a);
            double d = x-y;
            if(sgn(d) == 0)return 0;
            p = ((u.s*x)-(u.e*y))/d;
            return 1;
        }
        //`点到平面最近点(也就是投影)`
        Point3 pointtoplane(Point3 p)
        {
            Line3 u = Line3(p,p+o);
            crossline(u,p);
            return p;
        }
        //`平面和平面的交线`
        int crossplane(Plane f,Line3 &u)
        {
            Point3 oo = o^f.o;
            Point3 v = o^oo;
            double d = fabs(f.o*v);
            if(sgn(d) == 0)return 0;
            Point3 q = a + (v*(f.o*(f.a-a))/d);
            u = Line3(q,q+oo);
            return 1;
        }
    };

    平面最近点对

    const int MAXN = 100010;
    const double eps = 1e-8;
    const double INF = 1e20;
    struct Point{
        double x,y;
        void input(){
            scanf("%lf%lf",&x,&y);
        }
    };
    double dist(Point a,Point b){
        return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
    }
    Point p[MAXN];
    Point tmpt[MAXN];
    bool cmpx(Point a,Point b){
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
    bool cmpy(Point a,Point b){
        return a.y < b.y || (a.y == b.y && a.x < b.x);
    }
    double Closest_Pair(int left,int right){
        double d = INF;
        if(left == right)return d;
        if(left+1 == right)return dist(p[left],p[right]);
        int mid = (left+right)/2;
        double d1 = Closest_Pair(left,mid);
        double d2 = Closest_Pair(mid+1,right);
        d = min(d1,d2);
        int cnt = 0;
        for(int i = left;i <= right;i++){
            if(fabs(p[mid].x - p[i].x) <= d)
                tmpt[cnt++] = p[i];
        }
        sort(tmpt,tmpt+cnt,cmpy);
        for(int i = 0;i < cnt;i++){
            for(int j = i+1;j < cnt && tmpt[j].y - tmpt[i].y < d;j++)
                d = min(d,dist(tmpt[i],tmpt[j]));
        }
        return d;
    }
    int main(){
        int n;
        while(scanf("%d",&n) == 1 && n){
            for(int i = 0;i < n;i++)p[i].input();
            sort(p,p+n,cmpx);
            printf("%.2lf\n",Closest_Pair(0,n-1));
        }
        return 0;
    }

    三维凸包HDU4273

    const double eps = 1e-8;
    const int MAXN = 550;
    int sgn(double x){
        if(fabs(x) < eps)return 0;
        if(x < 0)return -1;
        else return 1;
    }
    struct Point3{
        double x,y,z;
        Point3(double _x = 0, double _y = 0, double _z = 0){
            x = _x;
            y = _y;
            z = _z;
        }
        void input(){
            scanf("%lf%lf%lf",&x,&y,&z);
        }
        bool operator ==(const Point3 &b)const{
            return sgn(x-b.x) == 0 && sgn(y-b.y) == 0 && sgn(z-b.z) == 0;
        }
        double len(){
            return sqrt(x*x+y*y+z*z);
        }
        double len2(){
            return x*x+y*y+z*z;
        }
        double distance(const Point3 &b)const{
            return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
        }
        Point3 operator -(const Point3 &b)const{
            return Point3(x-b.x,y-b.y,z-b.z);
        }
        Point3 operator +(const Point3 &b)const{
            return Point3(x+b.x,y+b.y,z+b.z);
        }
        Point3 operator *(const double &k)const{
            return Point3(x*k,y*k,z*k);
        }
        Point3 operator /(const double &k)const{
            return Point3(x/k,y/k,z/k);
        }
        //点乘
        double operator *(const Point3 &b)const{
            return x*b.x + y*b.y + z*b.z;
        }
        //叉乘
        Point3 operator ^(const Point3 &b)const{
            return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
        }
    };
    struct CH3D{
        struct face{
            //表示凸包一个面上的三个点的编号
            int a,b,c;
            //表示该面是否属于最终的凸包上的面
            bool ok;
        };
        //初始顶点数
        int n;
        Point3 P[MAXN];
        //凸包表面的三角形数
        int num;
        //凸包表面的三角形
        face F[8*MAXN];
        int g[MAXN][MAXN];
        //叉乘
        Point3 cross(const Point3 &a,const Point3 &b,const Point3 &c){
            return (b-a)^(c-a);
        }
        //`三角形面积*2`
        double area(Point3 a,Point3 b,Point3 c){
            return ((b-a)^(c-a)).len();
        }
        //`四面体有向面积*6`
        double volume(Point3 a,Point3 b,Point3 c,Point3 d){
            return ((b-a)^(c-a))*(d-a);
        }
        //`正:点在面同向`
        double dblcmp(Point3 &p,face &f){
            Point3 p1 = P[f.b] - P[f.a];
            Point3 p2 = P[f.c] - P[f.a];
            Point3 p3 = p - P[f.a];
            return (p1^p2)*p3;
        }
        void deal(int p,int a,int b){
            int f = g[a][b];
            face add;
            if(F[f].ok){
                if(dblcmp(P[p],F[f]) > eps)
                    dfs(p,f);
                else {
                    add.a = b;
                    add.b = a;
                    add.c = p;
                    add.ok = true;
                    g[p][b] = g[a][p] = g[b][a] = num;
                    F[num++] = add;
                }
            }
        }
        //递归搜索所有应该从凸包内删除的面
        void dfs(int p,int now){
            F[now].ok = false;
            deal(p,F[now].b,F[now].a);
            deal(p,F[now].c,F[now].b);
            deal(p,F[now].a,F[now].c);
        }
        bool same(int s,int t){
            Point3 &a = P[F[s].a];
            Point3 &b = P[F[s].b];
            Point3 &c = P[F[s].c];
            return fabs(volume(a,b,c,P[F[t].a])) < eps &&
                fabs(volume(a,b,c,P[F[t].b])) < eps &&
                fabs(volume(a,b,c,P[F[t].c])) < eps;
        }
        //构建三维凸包
        void create(){
            num = 0;
            face add;
    
            //***********************************
            //此段是为了保证前四个点不共面
            bool flag = true;
            for(int i = 1;i < n;i++){
                if(!(P[0] == P[i])){
                    swap(P[1],P[i]);
                    flag = false;
                    break;
                }
            }
            if(flag)return;
            flag = true;
            for(int i = 2;i < n;i++){
                if( ((P[1]-P[0])^(P[i]-P[0])).len() > eps ){
                    swap(P[2],P[i]);
                    flag = false;
                    break;
                }
            }
            if(flag)return;
            flag = true;
            for(int i = 3;i < n;i++){
                if(fabs( ((P[1]-P[0])^(P[2]-P[0]))*(P[i]-P[0]) ) > eps){
                    swap(P[3],P[i]);
                    flag = false;
                    break;
                }
            }
            if(flag)return;
            //**********************************
    
            for(int i = 0;i < 4;i++){
                add.a = (i+1)%4;
                add.b = (i+2)%4;
                add.c = (i+3)%4;
                add.ok = true;
                if(dblcmp(P[i],add) > 0)swap(add.b,add.c);
                g[add.a][add.b] = g[add.b][add.c] = g[add.c][add.a] = num;
                F[num++] = add;
            }
            for(int i = 4;i < n;i++)
                for(int j = 0;j < num;j++)
                    if(F[j].ok && dblcmp(P[i],F[j]) > eps){
                        dfs(i,j);
                        break;
                    }
            int tmp = num;
            num = 0;
            for(int i = 0;i < tmp;i++)
                if(F[i].ok)
                    F[num++] = F[i];
        }
        //表面积
        //`测试:HDU3528`
        double area(){
            double res = 0;
            if(n == 3){
                Point3 p = cross(P[0],P[1],P[2]);
                return p.len()/2;
            }
            for(int i = 0;i < num;i++)
                res += area(P[F[i].a],P[F[i].b],P[F[i].c]);
            return res/2.0;
        }
        double volume(){
            double res = 0;
            Point3 tmp = Point3(0,0,0);
            for(int i = 0;i < num;i++)
                res += volume(tmp,P[F[i].a],P[F[i].b],P[F[i].c]);
            return fabs(res/6);
        }
        //表面三角形个数
        int triangle(){
            return num;
        }
        //表面多边形个数
        //`测试:HDU3662`
        int polygon(){
            int res = 0;
            for(int i = 0;i < num;i++){
                bool flag = true;
                for(int j = 0;j < i;j++)
                    if(same(i,j)){
                        flag = 0;
                        break;
                    }
                res += flag;
            }
            return res;
        }
        //重心
        //`测试:HDU4273`
        Point3 barycenter(){
            Point3 ans = Point3(0,0,0);
            Point3 o = Point3(0,0,0);
            double all = 0;
            for(int i = 0;i < num;i++){
                double vol = volume(o,P[F[i].a],P[F[i].b],P[F[i].c]);
                ans = ans + (((o+P[F[i].a]+P[F[i].b]+P[F[i].c])/4.0)*vol);
                all += vol;
            }
            ans = ans/all;
            return ans;
        }
        //点到面的距离
        //`测试:HDU4273`
        double ptoface(Point3 p,int i){
            double tmp1 = fabs(volume(P[F[i].a],P[F[i].b],P[F[i].c],p));
            double tmp2 = ((P[F[i].b]-P[F[i].a])^(P[F[i].c]-P[F[i].a])).len();
            return tmp1/tmp2;
        }
    };
    CH3D hull;
    int main()
    {
        while(scanf("%d",&hull.n) == 1){
            for(int i = 0;i < hull.n;i++)hull.P[i].input();
            hull.create();
            Point3 p = hull.barycenter();
            double ans = 1e20;
            for(int i = 0;i < hull.num;i++)
                ans = min(ans,hull.ptoface(p,i));
            printf("%.3lf\n",ans);
        }
        return 0;
    }
    展开全文
  • 目录二维几何点线圆 二维几何 点 const double inf=1e20; const double eps=1e-8; const double pi=acos(-1.0); const int maxp=1010; //判断正负 int sgn(double x) { if (fabs(x)<eps) return 0; if (x<0...

    二维几何

    const double inf=1e20;
    const double eps=1e-8;
    const double pi=acos(-1.0);
    const int maxp=1010;
    
    //判断正负
    int sgn(double x) {
    	if (fabs(x)<eps) return 0;
    	if (x<0) return -1;
    	else return 1;
    }
    //平方
    inline double sqr(double x) {
    	return x*x;
    }
    
    struct Point {
    	double x,y;
    	Point() {}
    	Point(double _x, double _y) {
    		x=_x;
    		y=_y;
    	}
    	void input() {
    		scanf("%lf%lf",&x,&y);
    	}
    	void output() {
    		printf("%.2f%.2f\n",x,y);
    	}
    	bool operator == (Point b)const {
    		return sgn(x-b.x)==0 && sgn(y-b.y)==0;
    	}
    	bool operator < (Point b)const {
    		return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;
    	}
    	Point operator -(const Point &b)const {
    		return Point(x-b.x,y-b.y);
    	}
    	//叉积
    	double operator ^(const Point &b)const {
    		return x*b.y-y*b.x;
    	}
    	//点积
    	double operator *(const Point &b)const {
    		return x*b.x+y*b.y;
    	}
    	//返回长度
    	double len() {
    		return hypot(x,y);
    	}
    	//返回长度平方
    	double len2() {
    		return x*x+y*y;
    	}
    	//返回两点间距
    	double distance(Point p) {
    		return hypot(x-p.x,y-p.y);
    	}
    	Point operator +(const Point &b)const {
    		return Point(x+b.x,y+b.y);
    	}
    	Point operator *(const double &k)const {
    		return Point(x*k,y*k);
    	}
    	Point operator /(const double &k)const {
    		return Point(x/k,y/k);
    	}
    	//pa和pb的夹角
    	double rad(Point a,Point b) {
    		Point p=*this;
    		return fabs(atan2(fabs((a-p)^(b-p)),(a-p)*(b-p)));
    	}
    	//化为长度为r的向量
    	Point trunc(double r) {
    		double l=len();
    		if (!sgn(l)) return *this;
    		r/=l;
    		return Point(x*r,y*r);
    	}
    	//逆时针旋转 90 度
    	Point rotleft() {
    		return Point(-y,x);
    	}
    	//顺时针旋转 90 度
    	Point rotright() {
    		return Point(y,-x);
    	}
    	//绕着 p 点逆时针旋转 angle
    	Point rotate(Point p,double angle) {
    		Point v=(*this)-p;
    		double c=cos(angle),s=sin(angle);
    		return Point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
    	}
    };
    

    线

    struct Line {
    	Point s,e;
    	Line() {}
    	Line(Point _s,Point _e) {
    		s=_s;
    		e=_e;
    	}
    	bool operator ==(Line v) {
    		return (s==v.s) && (e==v.e);
    	}
    	//根据一个点和倾斜角 angle 确定直线,0<=angle<π
    	Line(Point p, double angle) {
    		s=p;
    		if (sgn(angle-pi/2)==0) {
    			e=(s+Point(0,1));
    		} 
    		else {
    			e=(s+Point(1,tan(angle)));
    		}
    	}
    	//ax+by+c=0
    	Line(double a,double b,double c) {
    		if(sgn(a)==0) {
    			s=Point(0,-c/b);
    			e=Point(1,-c/b);
    		} 
    		else if(sgn(b)==0) {
    			s=Point(-c/a,0);
    			e=Point(-c/a,1);
    		} 
    		else {
    			s=Point(0,-c/b);
    			e=Point(1,(-c-a)/b);
    		}
    	}
    	void input() {
    		s.input();
    		e.input();
    	}
    	void adjust() {
    		if(e<s) swap(s,e);	
    	}
    	//求线段长度
    	double length() {
    		return s.distance(e);
    	}
    	//返回直线倾斜角 0<=angle<π 
    	double angle() {
    		double k=atan2(e.y-s.y,e.x-s.x);
    		if(sgn(k)<0) k+=pi;
    		if(sgn(k-pi)==0) k-= pi;
    		return k;
    	}
    	//点和直线关系
    	// 1 在左侧
    	// 2 在右侧
    	// 3 在直线上 
    	int relation(Point p) {
    		int c=sgn((p-s)^(e-s));
    		if(c<0) return 1; 
    		else if(c>0) return 2; 
    		else return 3;	 
    	}
    	//点在线段上的判断
    	bool pointonseg(Point p) {
    		return sgn((p-s)^(e-s))==0 && sgn((p-s)*(p-e))<=0;
    	}
    	//两向量平行 (对应直线平行或重合)
    	bool parallel(Line v) {
    		return sgn((e-s)^(v.e-v.s))==0;
    	}
    	//两线段相交判断
    	//2 规范相交
    	//1 非规范相交
    	//0 不相交
    	int segcrossseg(Line v) {
    		int d1=sgn((e-s)^(v.s-s));
    		int d2=sgn((e-s)^(v.e-s));
    		int d3=sgn((v.e-v.s)^(s-v.s));
    		int d4=sgn((v.e-v.s)^(e-v.s));
    		if((d1^d2)==-2&&(d3^d4)==-2)return 2;
    		return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||
    		       (d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||
    		       (d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||
    		       (d4==0 && sgn((e-v.s)*(e-v.e))<=0);
    	}
    	//直线和线段相交判断
    	//-*this line -v seg
    	//2 规范相交
    	//1 非规范相交
    	//0 不相交
    	int linecrossseg(Line v) {
    		int d1=sgn((e-s)^(v.s-s));
    		int d2=sgn((e-s)^(v.e-s));
    		if((d1^d2)==-2) return 2;
    		return (d1==0||d2==0);
    	}
    	//两直线关系
    	//0 平行
    	//1 重合
    	//2 相交
    	int linecrossline(Line v) {
    		if((*this).parallel(v))
    			return v.relation(s)==3;
    		return 2;
    	}
    	//求两直线的交点
    	//要保证两直线不平行或重合
    	Point crosspoint(Line v) {
    		double a1 = (v.e-v.s)^(s-v.s);
    		double a2 = (v.e-v.s)^(e-v.s);
    		return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1
    		                                                     ));
    	}
    	//点到直线的距离
    	double dispointtoline(Point p) {
    		return fabs((p-s)^(e-s))/length();
    	}
    	//点到线段的距离
    	double dispointtoseg(Point p) {
    		if(sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0)
    			return min(p.distance(s),p.distance(e));
    		return dispointtoline(p);
    	}
    	//返回线段到线段的距离
    	//前提是两线段不相交,相交距离就是 0 了
    	double dissegtoseg(Line v) {
    		return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v
    		           .dispointtoseg(s),v.dispointtoseg(e)));
    	}
    	//返回点 p 在直线上的投影
    	Point lineprog(Point p) {
    		return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
    	}
    	//返回点 p 关于直线的对称点
    	Point symmetrypoint(Point p) {
    		Point q = lineprog(p);
    		return Point(2*q.x-p.x,2*q.y-p.y);
    	}
    };
    

    struct circle {
    	Point p; //圆心
    	double r; //半径
    	circle() {}
    	circle(Point _p,double _r) {
    		p=_p;
    		r=_r;
    	}
    	circle(double x,double y,double _r) {
    		p=Point(x,y);
    		r=_r;
    	}
    	//三角形的外接圆
    	//需要 Point 的 + / rotate() 以及 Line 的 crosspoint()
    	//利用两条边的中垂线得到圆心
    	circle(Point a,Point b,Point c) {
    		Line u=Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
    		Line v=Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
    		p=u.crosspoint(v);
    		r=p.distance(a);
    	}
    	//三角形的内切圆
    	//参数 bool t 没有作用,只是为了和上面外接圆函数区别
    	circle(Point a,Point b,Point c,bool t) {
    		Line u,v;
    		double m=atan2(b.y-a.y,b.x-a.x),n=atan2(c.y-a.y,c.x-a.x);
    		u.s=a;
    		u.e=u.s+Point(cos((n+m)/2),sin((n+m)/2));
    		v.s=b;
    		m=atan2(a.y-b.y,a.x-b.x),n=atan2(c.y-b.y,c.x-b.x);
    		v.e=v.s+Point(cos((n+m)/2),sin((n+m)/2));
    		p=u.crosspoint(v);
    		r=Line(a,b).dispointtoseg(p);
    	}
    	void input() {
    		p.input();
    		scanf("%lf",&r);
    	}
    	void output() {
    		printf("%.2lf-%.2lf-%.2lf\n",p.x,p.y,r);
    	}
    	bool operator == (circle v) {
    		return (p==v.p) && sgn(r-v.r)==0;
    	}
    	bool operator < (circle v)const {
    		return ((p<v.p) || ((p==v.p) && sgn(r-v.r)<0));
    	}
    	//面积
    	double area() {
    		return pi*r*r;
    	}
    	//周长
    	double circumference() {
    		return 2*pi*r;
    	}
    	//点和圆的关系
    	//0 圆外
    	//1 圆上
    	//2 圆内
    	int relation(Point b) {
    		double dst=b.distance(p);
    		if (sgn(dst-r)<0) return 2;
    		else if (sgn(dst-r)==0) return 1;
    		return 0;
    	}
    	//线段和圆的关系
    	//比较的是圆心到线段的距离和半径的关系
    	int relationseg(Line v) {
    		double dst=v.dispointtoseg(p);
    		if (sgn(dst-r)<0) return 2;
    		else if (sgn(dst-r)==0) return 1;
    		return 0;
    	}
    	//直线和圆的关系
    	//比较的是圆心到直线的距离和半径的关系
    	int relationline(Line v) {
    		double dst=v.dispointtoline(p);
    		if (sgn(dst-r)<0) return 2;
    		else if (sgn(dst-r)==0) return 1;
    		return 0;
    	}
    	//两圆的关系
    	//5 相离
    	//4 外切
    	//3 相交
    	//2 内切
    	//1 内含
    	//需要 Point 的 distance
    	int relationcircle(circle v) {
    		double d=p.distance(v.p);
    		if (sgn(d-r-v.r)>0) return 5;
    		if (sgn(d-r-v.r)==0) return 4;
    		double l=fabs(r-v.r);
    		if (sgn(d-r-v.r)<0 && sgn(d-l)>0) return 3;
    		if (sgn(d-l)==0) return 2;
    		if (sgn(d-l)<0) return 1;
    	}
    	//求两个圆的交点,返回 0 表示没有交点,返回 1 是一个交点,2 是两个交点
    	//需要 relationcircle
    	int pointcrosscircle(circle v,Point &p1,Point &p2) {
    		int rel=relationcircle(v);
    		if (rel==1 || rel==5)return 0;
    		double d=p.distance(v.p);
    		double l=(d*d+r*r-v.r*v.r)/(2*d);
    		double h=sqrt(r*r-l*l);
    		Point tmp=p+(v.p-p).trunc(l);
    		p1=tmp+((v.p-p).rotleft().trunc(h));
    		p2=tmp+((v.p-p).rotright().trunc(h));
    		if(rel==2 || rel==4)
    			return 1;
    		return 2;
    	}
    	//求直线和圆的交点,返回交点个数
    	int pointcrossline(Line v,Point &p1,Point &p2) {
    		if (!(*this).relationline(v)) return 0;
    		Point a=v.lineprog(p);
    		double d=v.dispointtoline(p);
    		d=sqrt(r*r-d*d);
    		if (sgn(d)==0) {
    			p1=a;
    			p2=a;
    			return 1;
    		}
    		p1=a+(v.e-v.s).trunc(d);
    		p2=a-(v.e-v.s).trunc(d);
    		return 2;
    	}
    	//得到过 a,b 两点,半径为 r1 的两个圆
    	int gercircle(Point a,Point b,double r1,circle &c1,circle &c2) {
    		circle x(a,r1),y(b,r1);
    		int t=x.pointcrosscircle(y,c1.p,c2.p);
    		if (!t) return 0;
    		c1.r=c2.r=r;
    		return t;
    	}
    	//得到与直线 u 相切,过点 q, 半径为 r1 的圆
    	int getcircle(Line u,Point q,double r1,circle &c1,circle &c2) {
    		double dis = u.dispointtoline(q);
    		if (sgn(dis-r1*2)>0) return 0;
    		if (sgn(dis)==0) {
    			c1.p=q+((u.e-u.s).rotleft().trunc(r1));
    			c2.p=q+((u.e-u.s).rotright().trunc(r1));
    			c1.r=c2.r=r1;
    			return 2;
    		}
    
    		Line u1=Line((u.s+(u.e-u.s).rotleft().trunc(r1)),(u.e+(u.e-u.s).rotleft().trunc(r1)));
    		Line u2=Line((u.s + (u.e-u.s).rotright().trunc(r1)),(u.e+(u.e-u.s).rotright().trunc(r1)));
    		circle cc=circle(q,r1);
    		Point p1,p2;
    		if (!cc.pointcrossline(u1,p1,p2))
    			cc.pointcrossline(u2,p1,p2);
    		c1=circle(p1,r1);
    		if (p1==p2) {
    			c2=c1;
    			return 1;
    		}
    		c2=circle(p2,r1);
    		return 2;
    	}
    	//同时与直线 u,v 相切,半径为 r1 的圆
    	int getcircle (Line u,Line v,double r1,circle &c1,circle &c2,circle &c3,circle &c4) {
    		if(u.parallel(v))return 0;//两直线平行
    		Line u1=Line(u.s+(u.e-u.s).rotleft().trunc(r1),u.e+(u.e-u.s).rotleft().trunc(r1));
    		Line u2=Line(u.s+(u.e-u.s).rotright().trunc(r1),u.e+(u.e-u.s).rotright().trunc(r1));
    		Line v1=Line(v.s+(v.e-v.s).rotleft().trunc(r1),v.e+(v.e-v.s).rotleft().trunc(r1));
    		Line v2=Line(v.s+(v.e-v.s).rotright().trunc(r1),v.e+(v.e-v.s).rotright().trunc(r1));
    		c1.r=c2.r=c3.r=c4.r=r1;
    		c1.p=u1.crosspoint(v1);
    		c2.p=u1.crosspoint(v2);
    		c3.p=u2.crosspoint(v1);
    		c4.p=u2.crosspoint(v2);
    		return 4;
    	}
    	//同时与不相交圆 cx,cy 相切,半径为 r1 的圆
    	int getcircle(circle cx,circle cy,double r1,circle &c1,circle &c2) {
    		circle x(cx.p,r1+cx.r),y(cy.p,r1+cy.r);
    		int t=x.pointcrosscircle(y,c1.p,c2.p);
    		if (!t) return 0;
    		c1.r=c2.r=r1;
    		return t;
    	}
    
    	//过一点作圆的切线 (先判断点和圆的关系)
    	int tangentline(Point q,Line &u,Line &v) {
    		int x=relation(q);
    		if (x==2) return 0;
    		if (x==1) {
    			u=Line(q,q+(q-p).rotleft());
    			v=u;
    			return 1;
    		}
    		double d=p.distance(q);
    		double l=r*r/d;
    		double h=sqrt(r*r-l*l);
    		u=Line(q,p+((q-p).trunc(l)+(q-p).rotleft().trunc(h)));
    		v=Line(q,p+((q-p).trunc(l)+(q-p).rotright().trunc(h)));
    		return 2;
    	}
    	//求两圆相交的面积
    	double areacircle(circle v) {
    		int rel=relationcircle(v);
    		if (rel>=4) return 0.0;
    		if (rel<=2) return min(area(),v.area());
    		double d=p.distance(v.p);
    		double hf=(r+v.r+d)/2.0;
    		double ss=2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
    		double a1=acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
    		a1=a1*r*r;
    		double a2=acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
    		a2=a2*v.r*v.r;
    		return a1+a2-ss;
    	}
    	//求圆和三角形 pab 的相交面积
    	double areatriangle(Point a,Point b) {
    		if (sgn((p-a)^(p-b))==0) return 0.0;
    		Point q[5];
    		int len=0;
    		q[len++]=a;
    		Line l(a,b);
    		Point p1,p2;
    		if (pointcrossline(l,q[1],q[2])==2) {
    			if (sgn((a-q[1])*(b-q[1]))<0) q[len++]=q[1];
    			if (sgn((a-q[2])*(b-q[2]))<0) q[len++]=q[2];
    		}
    		q[len++]=b;
    		if (len==4 && sgn((q[0]-q[1])*(q[2]-q[1]))>0) swap(q[1],q[2]);
    		double res=0;
    		for (int i=0; i<len-1; i++) {
    			if (relation(q[i])==0||relation(q[i+1])==0) {
    				double arg=p.rad(q[i],q[i+1]);
    				res+=r*r*arg/2.0;
    			} 
    			else {
    				res+=fabs((q[i]-p)^(q[i+1]-p))/2.0;
    			}
    		}
    		return res;
    	}
    };
    

    多边形

    struct polygon {
    	int n;
    	Point p[maxp];
    	Line l[maxp];
    	void input(int _n) {
    		n=_n;
    		for (int i=0; i<n; i++)
    			p[i].input();
    	}
    	void add(Point q) {
    		p[n++]=q;
    	}
    	void getline() {
    		for(int i=0; i<n; i++) {
    			l[i]=Line(p[i],p[(i+1)%n]);
    		}
    	}
    	struct cmp {
    		Point p;
    		cmp(const Point &p0) {
    			p=p0;
    		}
    		bool operator()(const Point &aa,const Point &bb) {
    			Point a=aa, b = bb;
    			int d=sgn((a-p)^(b-p));
    			if(d==0) {
    				return sgn(a.distance(p)-b.distance(p))<0;
    			}
    			return d>0;
    		}
    	};
    	//进行极角排序
    	//首先需要找到最左下角的点
    	//需要重载号好 Point 的 < 操作符 (min 函数要用)
    	void norm() {
    		Point mi=p[0];
    		for (int i=1; i<n; i++) 
    			mi=min(mi,p[i]);
    		sort(p,p+n,cmp(mi));
    	}
    	//得到凸包
    	//得到的凸包里面的点编号是 0~n-1 的
    	//两种凸包的方法
    	//注意如果有影响,要特判下所有点共点,或者共线的特殊情况
    	void getconvex(polygon &convex) {
    		sort(p,p+n);
    		convex.n=n;
    		for (int i=0; i<min(n,2); i++) {
    			convex.p[i]=p[i];
    		}
    		if (convex.n==2 && (convex.p[0]==convex.p[1]))
    			convex.n--;//特判
    		if (n <= 2) return;
    		int &top=convex.n;
    		top=1;
    		for (int i=2; i<n; i++) {
    			while (top && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<=0)
    				top--;
    			convex.p[++top]=p[i];
    		}
    		int temp=top;
    		convex.p[++top]=p[n-2];
    		for (int i=n-3; i>=0; i--) {
    			while (top!=temp && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<=0)
    				top--;
    			convex.p[++top]=p[i];
    		}
    		if (convex.n==2 && (convex.p[0]==convex.p[1]))
    			convex.n--;//特判
    		convex.norm();//原来得到的是顺时针的点,排序后逆时针
    	}
    	//得到凸包的另外一种方法
    	void Graham(polygon &convex) {
    		norm();
    		int &top=convex.n;
    		top=0;
    		if (n==1) {
    			top=1;
    			convex.p[0]=p[0];
    			return;
    		}
    		if (n==2) {
    			top=2;
    			convex.p[0]=p[0];
    			convex.p[1]=p[1];
    			if(convex.p[0]==convex.p[1]) top--;
    			return;
    		}
    		convex.p[0]=p[0];
    		convex.p[1]=p[1];
    		top=2;
    		for (int i=2; i<n; i++) {
    			while ( top>1 && sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2]))<=0)
    				top--;
    			convex.p[top++]=p[i];
    		}
    		if (convex.n==2 && (convex.p[0]==convex.p[1]))
    			convex.n--;//特 判
    	}
    	//判断是不是凸的
    	bool isconvex() {
    		bool s[2];
    		memset(s,false,sizeof(s));
    		for (int i=0; i<n; i++) {
    			int j=(i+1)%n;
    			int k=(j+1)%n;
    			s[sgn((p[j]-p[i])^(p[k]-p[i]))+1]=true;
    			if (s[0] && s[2]) return false;
    		}
    		return true;
    	}
    	//判断点和任意多边形的关系
    	// 3 点上
    	// 2 边上
    	// 1 内部
    	// 0 外部
    	int relationpoint(Point q) {
    		for (int i=0; i<n; i++) {
    			if (p[i]==q) return 3;
    		}
    		getline();
    		for (int i=0; i<n; i++) {
    			if (l[i].pointonseg(q)) return 2;
    		}
    		int cnt=0;
    		for (int i=0; i<n; i++) {
    			int j=(i+1)%n;
    			int k=sgn((q-p[j])^(p[i]-p[j]));
    			int u=sgn(p[i].y-q.y);
    			int v=sgn(p[j].y-q.y);
    			if (k>0 && u<0 && v>=0) cnt++;
    			if (k<0 && v<0 && u>=0) cnt--;
    		}
    		return cnt!=0;
    	}
    	//直线 u 切割凸多边形左侧
    	//注意直线方向
    	void convexcut(Line u,polygon &po) {
    		int &top=po.n;//注意引用
    		top=0;
    		for (int i=0; i<n; i++) {
    			int d1=sgn((u.e-u.s)^(p[i]-u.s));
    			int d2=sgn((u.e-u.s)^(p[(i+1)%n]-u.s));
    			if (d1>=0) po.p[top++]=p[i];
    			if (d1*d2<0) 
    				po.p[top++] = u.crosspoint(Line(p[i],p[(i+1)%n]));
    		}
    	}
    	//得到周长
    	double getcircumference() {
    		double sum=0;
    		for (int i=0; i<n; i++) {
    			sum+=p[i].distance(p[(i+1)%n]);
    		}
    		return sum;
    	}
    	//得到面积
    	double getarea() {
    		double sum=0;
    		for (int i=0; i<n; i++) {
    			sum+=(p[i]^p[(i+1)%n]);
    		}
    		return fabs(sum)/2;
    	}
    	//得到方向
    	// 1 表示逆时针,0 表示顺时针
    	bool getdir() {
    		double sum=0;
    		for (int i=0; i<n; i++)
    			sum+=(p[i]^p[(i+1)%n]);
    		if (sgn(sum)>0) return 1;
    		return 0;
    	}
    	//得到重心
    	Point getbarycentre() {
    		Point ret(0,0);
    		double area=0;
    		for (int i=1; i<n-1; i++) {
    			double tmp=(p[i]-p[0])^(p[i+1]-p[0]);
    			if (sgn(tmp)==0)continue;
    			area+=tmp;
    			ret.x+=(p[0].x+p[i].x+p[i+1].x)/3*tmp;
    			ret.y+=(p[0].y+p[i].y+p[i+1].y)/3*tmp;
    		}
    		if (sgn(area)) ret=ret/area;
    		return ret;
    	}
    	//多边形和圆交的面积
    	double areacircle(circle c) {
    		double ans=0;
    		for (int i=0; i<n; i++) {
    			int j=(i+1)%n;
    			if (sgn((p[j]-c.p)^(p[i]-c.p))>=0)
    				ans+=c.areatriangle(p[i],p[j]);
    			else ans-=c.areatriangle(p[i],p[j]);
    		}
    		return fabs(ans);
    	}
    	//多边形和圆关系
    	// 2 圆完全在多边形内
    	// 1 圆在多边形里面,碰到了多边形边界
    	// 0 其它
    	int relationcircle(circle c) {
    		getline();
    		int x=2;
    		if (relationpoint(c.p) != 1) return 0;//圆心不在内部
    		for (int i=0; i<n; i++) {
    			if (c.relationseg(l[i])==2) return 0;
    			if (c.relationseg(l[i])==1) x=1;
    		}
    		return x;
    	}
    };
    

    其他

    向量运算

    //AB X AC
    double cross(Point A,Point B,Point C) {
    	return (B-A)^(C-A);
    }
    //AB*AC
    double dot(Point A,Point B,Point C) {
    	return (B-A)*(C-A);
    }
    

    最小面积覆盖

    // A 必须是凸包 (而且是逆时针顺序)
    double minRectangleCover(polygon A) {
    	//要特判 A.n < 3 的情况
    	if (A.n<3) return 0.0;
    	A.p[A.n]=A.p[0];
    	double ans=-1;
    	int r=1,p=1,q;
    	for(int i=0; i<A.n; i++) {
    		//卡出离边 A.p[i] - A.p[i+1] 最远的点
    		while (sgn(cross(A.p[i],A.p[i+1],A.p[r+1])-cross(A.p[i],A.p[i+1],A.p[r]))>=0)
    			r=(r+1)%A.n;
    		//卡出 A.p[i] - A.p[i+1] 方向上正向 n 最远的点
    		while (sgn(dot(A.p[i],A.p[i+1],A.p[p+1])-dot(A.p[i],A.p[i+1],A.p[p]))>=0)
    			p=(p+1)%A.n;
    		if (i==0) q=p;
    		//卡出 A.p[i] - A.p[i+1] 方向上负向最远的点
    		while (sgn(dot(A.p[i],A.p[i+1],A.p[q+1])-dot(A.p[i],A.p[i+1],A.p[q]))<=0)
    			q=(q+1)%A.n;
    		double d=(A.p[i]-A.p[i+1]).len2();
    		double tmp=cross(A.p[i],A.p[i+1],A.p[r])*(dot(A.p[i],A.p[i+1],A.p[p])-dot(A.p[i],A.p[i+1],A.p[q]))/d;
    		if (ans<0 || ans>tmp) ans=tmp;
    	}
    	return ans;
    }
    

    直线切凸多边形

    //多边形是逆时针的,在 q1q2 的左侧
    vector<Point> convexCut(const vector<Point> &ps,Point q1,Point q2) {
    	vector<Point>qs;
    	int n=ps.size();
    	for (int i=0; i<n; i++) {
    		Point p1=ps[i],p2=ps[(i+1)%n];
    		int d1=sgn((q2-q1)^(p1-q1)),d2=sgn((q2-q1)^(p2-q1));
    		if (d1>=0)
    			qs.push_back(p1);
    		if (d1*d2<0)
    			qs.push_back(Line(p1,p2).crosspoint(Line(q1,q2)));
    	}
    	return qs;
    }
    

    半平面交

    struct halfplane:public Line {
    	double angle;
    	halfplane() {}
    	//表示向量 s->e 逆时针 (左侧) 的半平面
    	halfplane(Point _s,Point _e) {
    		s=_s;
    		e=_e;
    	}
    	halfplane(Line v) {
    		s=v.s;
    		e=v.e;
    	}
    	void calcangle() {
    		angle=atan2(e.y-s.y,e.x-s.x);
    	}
    	bool operator <(const halfplane &b)const {
    		return angle<b.angle;
    	}
    };
    struct halfplanes {
    	int n;
    	halfplane hp[maxp];
    	Point p[maxp];
    	int que[maxp];
    	int st,ed;
    	void push(halfplane tmp) {
    		hp[n++]=tmp;
    	}
    	//去重
    	void unique() {
    		int m=1;
    		for (int i=1; i<n; i++) {
    			if (sgn(hp[i].angle-hp[i-1].angle)!=0)
    				hp[m++]=hp[i];
    			else if(sgn((hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s))>0)
    				hp[m-1]=hp[i];
    		}
    		n=m;
    	}
    	bool halfplaneinsert() {
    		for (int i=0; i<n; i++) hp[i].calcangle();
    		sort(hp,hp+n);
    		unique();
    		que[st=0]=0;
    		que[ed=1]=1;
    		p[1]=hp[0].crosspoint(hp[1]);
    		for (int i=2; i<n; i++) {
    			while (st<ed && sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0)
    				ed--;
    			while (st<ed && sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0)
    				st++;
    			que[++ed]=i;
    			if (hp[i].parallel(hp[que[ed-1]])) return false;
    			p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
    		}
    		while (st<ed && sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0)
    			ed--;
    		while (st<ed && sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0)
    			st++;
    		if (st+1>=ed) return false;
    		return true;
    	}
    	//得到最后半平面交得到的凸多边形
    	//需要先调用 halfplaneinsert() 且返回 true
    	void getconvex(polygon &con) {
    		p[st]=hp[que[st]].crosspoint(hp[que[ed]]);
    		con.n=ed-st+1;
    		for(int j=st,i=0; j<=ed; i++,j++)
    			con.p[i]=p[j];
    	}
    };
    

    多圆问题

    const int maxn = 1010;
    struct circles {
    	circle c[maxn];
    	double ans[maxn];//ans[i] 表示被覆盖了 i 次的面积
    	double pre[maxn];
    	int n;
    	circles() {}
    	void add(circle cc) {
    		c[n++]=cc;
    	}
    	//x 包含在 y 中
    	bool inner(circle x,circle y) {
    		if (x.relationcircle(y) != 1) return 0;
    		return sgn(x.r-y.r)<=0?1:0;
    	}
    	//圆的面积并去掉内含的圆
    	void init_or() {
    		bool mark[maxn]= {0};
    		int i,j,k=0;
    		for (i=0; i<n; i++) {
    			for (j=0; j<n; j++)
    				if (i!=j && !mark[j]) {
    					if ((c[i]==c[j]) || inner(c[i],c[j]))
    						break;
    				}
    			if (j<n) mark[i]=1;
    		}
    		for (i=0; i<n; i++)
    			if(!mark[i])
    				c[k++]=c[i];
    		n=k;
    	}
    	//圆的面积交去掉内含的圆
    	void init_add() {
    		int i,j,k;
    		bool mark[maxn] = {0};
    		for (i=0; i<n; i++) {
    			for (j=0; j<n; j++)
    				if (i!=j && !mark[j]) {
    					if ((c[i]==c[j]) || inner(c[j],c[i])) break;
    				}
    			if (j<n) mark[i]=1;
    		}
    		for (i=0; i<n; i++)
    			if (!mark[i])
    				c[k++]=c[i];
    		n=k;
    	}
    	//半径为 r 的圆,弧度为 th 对应的弓形的面积
    	double areaarc(double th,double r) {
    		return 0.5*r*r*(th-sin(th));
    	}
    	//测试 SPOJVCIRCLES SPOJCIRUT
    	//SPOJVCIRCLES 求 n 个圆并的面积,需要加上 init_or() 去掉重复圆(否则WA)
    	//SPOJCIRUT 是求被覆盖 k 次的面积,不能加 init_or()
    	//对于求覆盖多少次面积的问题,不能解决相同圆,而且不能 init_or()
    	//求多圆面积并,需要 init_or, 其中一个目的就是去掉相同圆
    	void getarea() {
    		memset(ans,0,sizeof(ans));
    		vector<pair<double,int> >v;
    		for(int i=0; i<n; i++) {
    			v.clear();
    			v.push_back(make_pair(-pi,1));
    			v.push_back(make_pair(pi,-1));
    			for (int j=0; j<n; j++)
    				if (i!=j) {
    					Point q=(c[j].p-c[i].p);
    					double ab=q.len(),ac=c[i].r,bc=c[j].r;
    					if (sgn(ab+ac-bc)<=0) {
    						v.push_back(make_pair(-pi,1));
    						v.push_back(make_pair(pi,-1));
    						continue;
    					}
    					if (sgn(ab+bc-ac)<=0) continue;
    					if (sgn(ab-ac-bc)>0) continue;
    					double th=atan2(q.y,q.x),fai=acos((ac*ac+ab*ab-bc*bc)/(2.0*ac*ab));
    					double a0=th-fai;
    					if (sgn(a0+pi)<0) a0+=2*pi;
    					double a1=th+fai;
    					if (sgn(a1-pi)>0) a1-=2*pi;
    					if (sgn(a0-a1)>0) {
    						v.push_back(make_pair(a0,1));
    						v.push_back(make_pair(pi,-1));
    						v.push_back(make_pair(-pi,1));
    						v.push_back(make_pair(a1,-1));
    					} else {
    						v.push_back(make_pair(a0,1));
    						v.push_back(make_pair(a1,-1));
    					}
    				}
    			sort(v.begin(),v.end());
    			int cur=0;
    			for (int j=0; j<v.size(); j++) {
    				if (cur && sgn(v[j].first-pre[cur])) {
    					ans[cur]+=areaarc(v[j].first-pre[cur],c[i].r);
    					ans[cur]+=0.5*(Point(c[i].p.x+c[i].r*cos(pre[cur]),c[i].p.y+c[i].r*sin(pre[cur]))
    					               ^Point(c[i].p.x+c[i].r*cos(v[j].first),c[i].p.y+c[i].r*sin(v[j].first)));
    				}
    				cur+=v[j].second;
    				pre[cur]=v[j].first;
    			}
    		}
    		for (int i=1; i<n; i++)
    			ans[i]-=ans[i+1];
    	}
    };
    

    平面最近点对

    HDU1007/ZOJ2107

    const int MAXN=100010;
    const double INF=1e20;
    struct Point {
    	double x,y;
    	void input() {
    		scanf("%lf%lf",&x,&y);
    	}
    };
    double dist(Point a,Point b) {
    	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
    }
    Point p[MAXN];
    Point tmpt[MAXN];
    bool cmpx(Point a,Point b) {
    	return a.x<b.x || (a.x==b.x && a.y<b.y);
    }
    bool cmpy(Point a,Point b) {
    	return a.y<b.y || (a.y==b.y && a.x<b.x);
    }
    double Closest_Pair(int left,int right) {
    	double d=INF;
    	if (left==right) return d;
    	if (left+1==right) return dist(p[left],p[right]);
    	int mid=(left+right)/2;
    	double d1=Closest_Pair(left,mid);
    	double d2=Closest_Pair(mid+1,right);
    	d=min(d1,d2);
    	int cnt=0;
    	for (int i=left; i<=right; i++) {
    		if (fabs(p[mid].x-p[i].x)<=d)
    			tmpt[cnt++]=p[i];
    	}
    	sort(tmpt,tmpt+cnt,cmpy);
    	for (int i=0; i<cnt; i++) {
    		for (int j=i+1; j<cnt && tmpt[j].y-tmpt[i].y<d; j++)
    			d=min(d,dist(tmpt[i],tmpt[j]));
    	}
    	return d;
    }
    int main() {
    	int n;
    	while(scanf("%d",&n)==1 && n) {
    		for(int i=0; i<n; i++) p[i].input();
    		sort(p,p+n,cmpx);
    		printf("%.2lf\n",Closest_Pair(0,n-1));
    	}
    	return 0;
    }
    
    
    

    三维几何

    const double eps=1e-8;
    int sgn(double x) {
    	if (fabs(x)<eps) return 0;
    	if (x<0) return-1;
    	else return 1;
    }
    struct Point3 {
    	double x,y,z;
    	Point3(double _x=0,double _y=0,double _z=0) {
    		x=_x;
    		y=_y;
    		z=_z;
    	}
    	void input() {
    		scanf("%lf%lf%lf",&x,&y,&z);
    	}
    	void output() {
    		scanf("%.2lf-%.2lf-%.2lf\n",x,y,z);
    	}
    	bool operator ==(const Point3 &b)const {
    		return sgn(x-b.x)==0 && sgn(y-b.y)==0 && sgn(z-b.z)==0;
    	}
    	bool operator <(const Point3 &b)const {
    		return sgn(x-b.x)==0?(sgn(y-b.y)==0?sgn(z-b.z)<0:y<b.y):x<b.x;
    	}
    	double len() {
    		return sqrt(x*x+y*y+z*z);
    	}
    	double len2() {
    		return x*x+y*y+z*z;
    	}
    	double distance(const Point3 &b)const {
    		return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z)
    		           );
    	}
    	Point3 operator-(const Point3 &b)const {
    		return Point3(x-b.x,y-b.y,z-b.z);
    	}
    	Point3 operator +(const Point3 &b)const {
    		return Point3(x+b.x,y+b.y,z+b.z);
    	}
    	Point3 operator *(const double &k)const {
    		return Point3(x*k,y*k,z*k);
    	}
    	Point3 operator /(const double &k)const {
    		return Point3(x/k,y/k,z/k);
    	}
    	//点乘
    	double operator *(const Point3 &b)const {
    		return x*b.x+y*b.y+z*b.z;
    	}
    	//叉乘
    	Point3 operator ^(const Point3 &b)const {
    		return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
    	}
    	double rad(Point3 a,Point3 b) {
    		Point3 p=(*this);
    		return acos(((a-p)*(b-p))/(a.distance(p)*b.distance(p)));
    	}
    	//变换长度
    	Point3 trunc(double r) {
    		double l=len();
    		if (!sgn(l)) return *this;
    		r/=l;
    		return Point3(x*r,y*r,z*r);
    	}
    };
    

    线

    struct Line3 {
    	Point3 s,e;
    	Line3() {}
    	Line3(Point3 _s,Point3 _e) {
    		s=_s;
    		e=_e;
    	}
    	bool operator ==(const Line3 v) {
    		return (s==v.s)&&(e==v.e);
    	}
    	void input() {
    		s.input();
    		e.input();
    	}
    	double length() {
    		return s.distance(e);
    	}
    	//点到直线距离
    	double dispointtoline(Point3 p) {
    		return ((e-s)^(p-s)).len()/s.distance(e);
    	}
    	//点到线段距离
    	double dispointtoseg(Point3 p) {
    		if (sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0)
    			return min(p.distance(s),e.distance(p));
    		return dispointtoline(p);
    	}
    	//返回点 p 在直线上的投影
    	Point3 lineprog(Point3 p) {
    		return s+(((e-s)*((e-s)*(p-s)))/((e-s).len2()));
    	}
    	//p 绕此向量逆时针 arg 角度
    	Point3 rotate(Point3 p,double ang) {
    		if (sgn(((s-p)^(e-p)).len())==0)return p;
    		Point3 f1=(e-s)^(p-s);
    		Point3 f2=(e-s)^(f1);
    		double len=((s-p)^(e-p)).len()/s.distance(e);
    		f1=f1.trunc(len);
    		f2=f2.trunc(len);
    		Point3 h=p+f2;
    		Point3 pp=h+f1;
    		return h+((p-h)*cos(ang))+((pp-h)*sin(ang));
    	}
    	//点在直线上
    	bool pointonseg(Point3 p) {
    		return sgn(((s-p)^(e-p)).len())==0 && sgn((s-p)*(e-p))==0;
    	}
    };
    

    struct Plane {
    	Point3 a,b,c,o;//平面上的三个点,以及法向量
    	Plane() {}
    	Plane(Point3 _a,Point3 _b,Point3 _c) {
    		a=_a;
    		b=_b;
    		c=_c;
    		o=pvec();
    	}
    	Point3 pvec() {
    		return (b-a)^(c-a);
    	}
    	//ax+by+cz+d = 0
    	Plane(double _a,double _b,double _c,double _d) {
    		o=Point3(_a,_b,_c);
    		if (sgn(_a)!=0)
    			a=Point3((-_d-_c-_b)/_a,1,1);
    		else if (sgn(_b)!=0)
    			a=Point3(1,(-_d-_c-_a)/_b,1);
    		else if (sgn(_c)!=0)
    			a Point3(1,1,(-_d-_a-_b)/_c);
    	}
    	//点在平面上的判断
    	bool pointonplane(Point3 p) {
    		return sgn((p-a)*o)==0;
    	}
    	//两平面夹角
    	double angleplane(Plane f) {
    		return acos(o*f.o)/(o.len()*f.o.len());
    	}
    	//平面和直线的交点,返回值是交点个数
    	int crossline(Line3 u,Point3 &p) {
    		double x=o*(u.e-a);
    		double y=o*(u.s-a);
    		double d=x-y;
    		if (sgn(d)==0) return 0;
    		p=((u.s*x)-(u.e*y))/d;
    		return 1;
    	}
    	//点到平面最近点 (也就是投影)
    	Point3 pointtoplane(Point3 p) {
    		Line3 u=Line3(p,p+o);
    		crossline(u,p);
    		return p;
    	}
    	//平面和平面的交线
    	int crossplane(Plane f,Line3 &u) {
    		Point3 oo=o^f.o;
    		Point3 v=o^oo;
    		double d=fabs(f.o*v);
    		if (sgn(d)==0)return 0;
    		Point3 q=a+(v*(f.o*(f.a-a))/d);
    		u=Line3(q,q+oo);
    		return 1;
    	}
    };
    

    三维凸包

    HDU 4273 给一个三维凸包,求重心到表面的最短距离。

    const double eps=1e-8;
    const int MAXN=550;
    int sgn(double x) {
    	if (fabs(x)<eps) return 0;
    	if (x<0) return-1;
    	else return 1;
    }
    struct Point3 {
    	double x,y,z;
    	Point3(double _x=0, double _y=0, double _z=0) {
    		x=_x;
    		y=_y;
    		z=_z;
    	}
    	void input() {
    		scanf("%lf%lf%lf",&x,&y,&z);
    	}
    	bool operator ==(const Point3 &b)const {
    		return sgn(x-b.x)==0 && sgn(y-b.y)==0 && sgn(z-b.z)==0;
    	}
    	double len() {
    		return sqrt(x*x+y*y+z*z);
    	}
    	double len2() {
    		return x*x+y*y+z*z;
    	}
    	double distance(const Point3 &b)const {
    		return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
    	}
    	Point3 operator-(const Point3 &b)const {
    		return Point3(x-b.x,y-b.y,z-b.z);
    	}
    	Point3 operator +(const Point3 &b)const {
    		return Point3(x+b.x,y+b.y,z+b.z);
    	}
    	Point3 operator *(const double &k)const {
    		return Point3(x*k,y*k,z*k);
    	}
    	Point3 operator /(const double &k)const {
    		return Point3(x/k,y/k,z/k);
    	}
    	//点乘
    	double operator *(const Point3 &b)const {
    		return x*b.x+y*b.y+z*b.z;
    	}
    	//叉乘
    	Point3 operator ^(const Point3 &b)const {
    		return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
    	}
    };
    struct CH3D {
    	struct face {
    		//表示凸包一个面上的三个点的编号
    		int a,b,c;
    		//表示该面是否属于最终的凸包上的面
    		bool ok;
    	};
    	//初始顶点数
    	int n;
    	Point3 P[MAXN];
    	//凸包表面的三角形数
    	int num;
    	//凸包表面的三角形
    	face F[8*MAXN];
    	int g[MAXN][MAXN];
    	//叉乘
    	Point3 cross(const Point3 &a,const Point3 &b,const Point3 &c) {
    		return (b-a)^(c-a);
    	}
    	//三角形面积 *2
    	double area(Point3 a,Point3 b,Point3 c) {
    		return ((b-a)^(c-a)).len();
    	}
    	//四面体有向面积 *6
    	double volume(Point3 a,Point3 b,Point3 c,Point3 d) {
    		return ((b-a)^(c-a))*(d-a);
    	}
    	//正:点在面同向
    	double dblcmp(Point3 &p,face &f) {
    		Point3 p1=P[f.b]-P[f.a];
    		Point3 p2=P[f.c]-P[f.a];
    		Point3 p3=p-P[f.a];
    		return (p1^p2)*p3;
    	}
    	void deal(int p,int a,int b) {
    		int f=g[a][b];
    		face add;
    		if (F[f].ok) {
    			if (dblcmp(P[p],F[f])>eps)
    				dfs(p,f);
    			else {
    				add.a=b;
    				add.b=a;
    				add.c=p;
    				add.ok=true;
    				g[p][b]=g[a][p]=g[b][a]=num;
    				F[num++]=add;
    			}
    		}
    	}
    	//递归搜索所有应该从凸包内删除的面
    	void dfs(int p,int now) {
    		F[now].ok=false;
    		deal(p,F[now].b,F[now].a);
    		deal(p,F[now].c,F[now].b);
    		deal(p,F[now].a,F[now].c);
    	}
    	bool same(int s,int t) {
    		Point3 &a=P[F[s].a];
    		Point3 &b=P[F[s].b];
    		Point3 &c=P[F[s].c];
    		return fabs(volume(a,b,c,P[F[t].a]))<eps &&
    		       fabs(volume(a,b,c,P[F[t].b]))<eps &&
    		       fabs(volume(a,b,c,P[F[t].c]))<eps;
    	}
    	//构建三维凸包
    	void create() {
    		num=0;
    		face add;
    		//***********************************
    		//此段是为了保证前四个点不共面
    		bool flag=true;
    		for (int i=1; i<n; i++) {
    			if (!(P[0]==P[i])) {
    				swap(P[1],P[i]);
    				flag=false;
    				break;
    			}
    		}
    		if (flag)return;
    		flag=true;
    		for (int i=2; i<n; i++) {
    			if(((P[1]-P[0])^(P[i]-P[0])).len()>eps) {
    				swap(P[2],P[i]);
    				flag=false;
    				break;
    			}
    		}
    		if (flag) return;
    		flag=true;
    		for (int i=3; i<n; i++) {
    			if (fabs(((P[1]-P[0])^(P[2]-P[0]))*(P[i]-P[0]))>eps) {
    				swap(P[3],P[i]);
    				flag=false;
    				break;
    			}
    		}
    		if (flag) return;
    		//**********************************
    
    		for (int i=0; i<4; i++) {
    			add.a=(i+1)%4;
    			add.b=(i+2)%4;
    			add.c=(i+3)%4;
    			add.ok=true;
    			if (dblcmp(P[i],add)>0) swap(add.b,add.c);
    			g[add.a][add.b]=g[add.b][add.c]=g[add.c][add.a]=num;
    			F[num++]=add;
    		}
    		for (int i=4; i<n; i++)
    			for (int j=0; j<num; j++)
    				if (F[j].ok && dblcmp(P[i],F[j])>eps) {
    					dfs(i,j);
    					break;
    				}
    		int tmp=num;
    		num=0;
    		for (int i=0; i<tmp; i++)
    			if (F[i].ok)
    				F[num++]=F[i];
    	}
    	//表面积
    	double area() {
    		double res=0;
    		if (n==3) {
    			Point3 p=cross(P[0],P[1],P[2]);
    			return p.len()/2;
    		}
    		for (int i=0; i<num; i++)
    			res+=area(P[F[i].a],P[F[i].b],P[F[i].c]);
    		return res/2.0;
    	}
    	//体积
    	double volume() {
    		double res=0;
    		Point3 tmp=Point3(0,0,0);
    		for (int i=0; i<num; i++)
    			res+=volume(tmp,P[F[i].a],P[F[i].b],P[F[i].c]);
    		return fabs(res/6);
    	}
    	//表面三角形个数
    	int triangle() {
    		return num;
    	}
    	//表面多边形个数
    	int polygon() {
    		int res=0;
    		for (int i=0; i<num; i++) {
    			bool flag=true;
    			for (int j=0; j<i; j++)
    				if (same(i,j)) {
    					flag=0;
    					break;
    				}
    			res+=flag;
    		}
    		return res;
    	}
    	//重心
    	Point3 barycenter() {
    		Point3 ans=Point3(0,0,0);
    		Point3 o=Point3(0,0,0);
    		double all=0;
    		for (int i=0; i<num; i++) {
    			double vol=volume(o,P[F[i].a],P[F[i].b],P[F[i].c]);
    			ans=ans+(((o+P[F[i].a]+P[F[i].b]+P[F[i].c])/4.0)*vol);
    			all+=vol;
    		}
    		ans=ans/all;
    		return ans;
    	}
    	//点到面的距离
    	double ptoface(Point3 p,int i) {
    		double tmp1=fabs(volume(P[F[i].a],P[F[i].b],P[F[i].c],p));
    		double tmp2=((P[F[i].b]-P[F[i].a])^(P[F[i].c]-P[F[i].a])).len();
    		return tmp1/tmp2;
    	}
    };
    CH3D hull;
    int main() {
    	while(scanf("%d",&hull.n)==1) {
    		for(int i=0; i<hull.n; i++) hull.P[i].input();
    		hull.create();
    		Point3 p=hull.barycenter();
    		double ans=1e20;
    		for(int i=0; i<hull.num; i++)
    			ans=min(ans,hull.ptoface(p,i));
    		printf("%.3lf\n",ans);
    	}
    	return 0;
    }
    
    展开全文
  • 计算几何我觉得一靠板子,二靠细节。我会在另一篇博客整理出比较好的板子。细节得要自己培养培养,总不能总看网上的数据来过题呀。 C - Segments 题目大意:给出n条线段两个端点的坐标,问所有线段投影到一条直线...

    感觉做完没什么进步,不会做的题就去搜题解,没过的题就去找数据。。。下次不能这样!
    计算几何我觉得一靠板子,二靠细节。我会在另一篇博客整理出比较好的板子。细节得要自己培养培养,总不能总看网上的数据来过题呀。
    C - Segments
    题目大意:给出n条线段两个端点的坐标,问所有线段投影到一条直线上,如果这些所有投影至少相交于一点就输出Yes!,否则输出No!。
    解题思路:如果有存在这样的直线,过投影相交区域作直线的垂线,该垂线必定与每条线段相交,问题转化为问是否存在一条线和所有线段相交.
    直线肯定经过两个端点。
    枚举端点,判断直线和线段是否相交。
    细节要注意,判断重合点。
    还有就是加入只有一条线段的话,刚好直线是过同一条直线的。
    所以保险的做法是枚举所有的两个端点,包括同一条直线的。(kuangbin的题解)
    枚举端点是个常见的思路,往往端点就是极端情况。。

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<stdio.h>
    #include<set>
    using namespace std;
    const double eps = 1e-8;
    struct point
    {
        int index;
        double ang;
        double x, y;
        point() { x = 0;y = 0; }
        point(double sx, double sy) { x = sx, y = sy; }
        bool operator<(const point &b)const
        {
            if (x != b.x)return x < b.x;
            return y < b.y;
        }
    
    };
    struct line
    {
        double ang;
        point a, b;line(){}
        line(const point &p1, const point &p2)
        {
            a = p1;
            b = p2;
        }
    };
    
    
    double xmult(point p1, point p2, point p0)
    {
        return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
    }
    
    int opposite_side(point p1, point p2,line l)
    {
        double tmp = xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b);
        return  tmp < -eps || tmp < eps;
    }
    set<point>S;
    line lines[105];
    int n;
    bool check(line a)
    {
        for (int i = 1;i <= n;i++)
        {
            point tmp1 = lines[i].a;
            point tmp2 = lines[i].b;
            if (!opposite_side(tmp1, tmp2, a))
                return 0;
        }
        return 1;
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while (T--)
        {
            S.clear();
    
            scanf("%d", &n);
            double x1, y1, x2, y2;
            for (int i = 1;i <= n;i++)
            {
                scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
                S.insert(point(x1, y1));
                S.insert(point(x2, y2));
                lines[i] = line(point(x1, y1), point(x2, y2));
            }
            set<point>::iterator itor,itor2;
            bool flag = false;
            for(itor=S.begin();itor!=S.end();itor++)
                for (itor2 = itor;itor2 != S.end();itor2++)
                {
                    if (itor2 == itor)continue;
                    line tmp = line(*itor, *itor2);
                    if (check(tmp))
                    {
                        flag = true;
                        puts("Yes!");
                        itor = S.end();
                        itor--;
                        break;
                    }
                }
            if (!flag)
                puts("No!");
        }
    
    
    }
    

    E - The Doors
    这题应该能做出来的,当时蠢了一下。。先计算出端点到其他能到的点的距离,然后跑最短路就行了。

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<vector>
    #include<queue>
    using namespace std;
    
    #define eps 1e-8
    #define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
    #define zero(x) (fabs(x)<eps)
    
    struct point
    {
        int index;
        double x, y;
        point() { x = 0, y = 0; }
        point(double sx, double sy)
        {
            x = sx;
            y = sy;
        }
    };
    
    struct line
    {
        point a, b;
        line() {}
        line(const point &p1, const point &p2)
        {
            a = p1;
            b = p2;
        }
    };
    vector<line>V;
    
    double xmult(point p1, point p2, point p0)
    {
        return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
    }
    
    int opposite_side(point p1, point p2, line l)
    {
        return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) < -eps;
    }
    
    int intersect_ex(line u, line v)
    {
        return opposite_side(u.a, u.b, v) && opposite_side(v.a, v.b, u);
    }
    
    int parallel(line u, line v)
    {
        return zero((u.a.x - u.b.x)*(v.a.y - v.b.y) - (v.a.x - v.b.x)*(u.a.y - u.b.y));
    }
    
    double dist(line a)
    {
        double x = a.a.x - a.b.x;
        double y = a.a.y - a.b.y;
        return sqrt(x*x + y*y);
    }
    
    point P[100];
    int pcnt;
    double map[100][100];
    void buildmap()
    {
        for(int i=1;i<=pcnt;i++)
            for (int j = i + 1;j <= pcnt;j++)
            {
                map[i][j] = map[j][i] = 50.0;
                line tmp = line(P[i], P[j]);
                bool flag = true;
                for (int k = 0;k < V.size();k++)
                {
                    line tmp2 = V[k];
                    if (parallel(tmp, tmp2))continue;
                    if (intersect_ex(tmp, tmp2))
                    {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    map[i][j] = map[j][i] = dist(tmp);
            }
    }
    bool vis[100];
    double d[100];
    
    struct HeapNode
    {
        int u;
        double d;
        HeapNode(int _u,double _d):u(_u),d(_d){}
        HeapNode(){}
        bool operator<(const HeapNode &b)const
        {
            return d > b.d;
        }
    };
    
    double dijkstra()
    {
        memset(vis, 0, sizeof(vis));
        for (int i = 1;i <= pcnt;i++)d[i] = 50;
        d[1] = 0;
        priority_queue<HeapNode>Q;
        Q.push(HeapNode(1,d[1]));
        while (!Q.empty())
        {
            HeapNode x = Q.top();Q.pop();
            if (vis[x.u])continue;
            vis[x.u] = 1;
            for (int i = 1;i <= pcnt;i++)if(map[x.u][i]!=50)
            {
                if (d[i] > d[x.u] + map[x.u][i])
                {
                    d[i] = d[x.u] + map[x.u][i];
                    Q.push(HeapNode(i, d[i]));
                }
            }
        }
        return d[2];
    }
    
    int main()
    {
        int n;
        while (~scanf("%d", &n) && n != -1)
        {
            pcnt = 0;
            V.clear();
            double tmp1, tmp2, tmp3;
            //line tmp;
            P[++pcnt] = point(0, 5);
            P[++pcnt] = point(10, 5);
            for (int i = 1;i <= n;i++)
            {
                scanf("%lf %lf", &tmp1, &tmp2);
                //P[++pcnt] = point(tmp1, 0);
                P[++pcnt] = point(tmp1, tmp2);
                V.push_back(line(point(tmp1, 0), point(tmp1, tmp2)));
                scanf("%lf %lf", &tmp2, &tmp3);
                P[++pcnt] = point(tmp1, tmp2);
                P[++pcnt] = point(tmp1, tmp3);
                V.push_back(line(point(tmp1, tmp2), point(tmp1, tmp3)));
                scanf("%lf", &tmp2);
                P[++pcnt] = point(tmp1, tmp2);
                V.push_back(line(point(tmp1, tmp2), point(tmp1, 10)));
            }
            buildmap();
            printf("%.2f\n", dijkstra());
        }
    
    
    }
    

    G - Treasure Hunt
    这题一开始我的思路想着把它转换成最短路,不同的房间如果隔着一个墙就连条边,然后和最外面的再连一条边,这样就可以求最短路了。但想了很久不知道怎么划分房间。。
    正解还是枚举端点,端点和终点相连的线段看与多少个墙相交(不包括端点)。

    #include<iostream>
    #include<algorithm>
    #include<stdio.h>
    #include<cstring>
    using namespace std;
    #define eps 1e-5
    struct point
    {
        double x, y;
        point() { x = 0, y = 0; }
        point(double sx, double sy)
        {
            x = sx;
            y = sy;
        }
    }P[100];
    int now;
    struct line
    {
        point a, b;
        line(){}
        line(point p1, point p2)
        {
            a = p1;
            b = p2;
        }
    }lines[35];
    double aimx, aimy;
    int n;
    
    double xmult(point p1, point p2, point p0)
    {
        return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
    }
    
    int opposite_side(point p1, point p2, line l)
    {
        return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) < -eps;
    }
    
    int intersect_ex(line u, line v)
    {
        return opposite_side(u.a, u.b, v) && opposite_side(v.a, v.b, u);
    }
    
    void solve()
    {
        if (n == 0) { printf("Number of doors = 1\n");return; }
        int ans = 35;
        point aim = point(aimx, aimy);
        for (int i = 1;i <= now;i++)
        {
            line tmp = line(P[i], aim);
            int ctch = 0;
            for (int j = 1;j <= n;j++)
            {
                if (intersect_ex(tmp, lines[j]))
                    ctch++;
            }
            ans = min(ans, ctch);
        }
        printf("Number of doors = %d\n", ans+1);
    }
    
    int main()
    {
    
        scanf("%d", &n);
        int x1, y1, x2, y2;
        now = 0;
        for (int i = 1;i <= n;i++)
        {
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            P[++now] = point(x1, y1);
            P[++now] = point(x2, y2);
            lines[i] = line(P[now - 1], P[now]);
        }
        scanf("%lf %lf", &aimx, &aimy);
        solve();
    }

    H - Intersection
    本专题傻题之一。题目挺简单的,但这题有几个坑点。
    1,给出的矩形的两个点并不一定是按照顺序给出的,需要自己判断。
    2,线段在矩形内部也算相交(无语)。

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    using namespace std;
    #define eps 1e-5
    #define zero(x) (fabs(x)<eps)
    struct point
    {
        int x, y;
        point() { x = 0, y = 0; }
        point(int sx, int sy) { x = sx;y = sy; }
    };
    int xmult(point p1, point p2, point p0)
    {
        return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
    }
    
    struct line
    {
        point a, b;
        line() {}
        line(point _a, point _b) :a(_a), b(_b) {}
    };
    
    int dots_inline(point p1, point p2, point p3)
    {
        return zero(xmult(p1, p2, p3));
    }
    
    int same_side(point p1, point p2, line l)
    {
        return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps;
    }
    
    int dot_online_in(point p, line l)
    {
        return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x)*(l.b.x - p.x) < eps && (l.a.y - p.y)*(l.b.y - p.y) < eps;
    }
    
    int intersect_in(line u, line v)
    {
        if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
            return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
        return dot_online_in(u.a, v) || dot_online_in(u.b, v) || dot_online_in(v.a, u) || dot_online_in(v.b, u);
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while (T--)
        {
            int x1, y1, x2, y2;
            int x3, y3, x4, y4;
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            line a = line(point(x1, y1), point(x2, y2));
            scanf("%d %d %d %d", &x3, &y3, &x4, &y4);
            if (x3 > x4)swap(x3, x4);
            if (y3 < y4)swap(y3, y4);
            point a1 = point(x3, y3), a2 = point(x4, y3), a3 = point(x3, y4), a4 = point(x4, y4);
            line l1 = line(a1, a2), l2 = line(a1, a3), l3 = line(a3, a4), l4 = line(a2, a4);
            if (!intersect_in(a, l1) && !intersect_in(a, l2) && !intersect_in(a, l3) && !intersect_in(a, l4))
            {
                point tmp = a.a;
                if (tmp.x<x4&&tmp.x>x3&&tmp.y<y3&&tmp.y>y4)
                    puts("T");
                else
                    puts("F");
    
            }
            else
                puts("T");
        }
    }
    

    I - Space Ant
    一开始的思路没错,但是样例都没过,就发现我对极角排序有一点错误的理解。叉积极角排序只能排不超过π范围的点,如果超过了就得先按照象限排,再叉积极角排序。
    另外atan2那种排序方式范围是-π到π,换句话说就是从第三象限排(如果我没搞错的话)。

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    using namespace std;
    
    #define eps 1e-5
    #define zero(x) (fabs(x)<eps)
    
    
    struct point
    {
        int index;
        int x, y;
        point(){}
        point(int _x,int _y,int idx):x(_x),y(_y),index(idx){}
    };
    
    int xmult(point p1, point p2, point p0)
    {
        return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
    }
    
    double dist(point a, point b)
    {
        double x = a.x - b.x;
        double y = a.y - b.y;
        return sqrt(x*x + y*y);
    }
    
    struct line
    {
        point a, b;
        double ang;
        line(point sa, point sb)
        {
            a = sa;
            b = sb;
        }
        line(){}
        bool operator<(const line &y)const
        {
            if (zero(ang - y.ang))
            {
                return dist(a, b) < dist(y.a, y.b);
            }
            return ang < y.ang;
        }
        void getang()
        {
            ang = atan2(-b.y + a.y, -b.x + a.x);
        }
    };
    point P[105];
    int N;
    int ans[105];
    int cnt;
    point now;
    bool cmp(const point &a, const point &b)
    {
        int tmp = xmult(a, b, now);
        if (tmp == 0)
            return dist(a, now) < dist(b, now);
        return tmp > 0;
    }
    void solve(int themin)
    {
        cnt = 0;
    
        now = point(0, themin,0);
        for (int i = 1;i <= N;i++)
        {
            sort(P + i, P + N + 1,cmp);
            ans[++cnt] = P[i].index;
            now = P[i];
        }
        printf("%d", N);
        for (int i = 1;i <= N;i++)
            printf(" %d", ans[i]);
        puts("");
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while (T--)
        {
    
            scanf("%d", &N);
            int idx, x, y;
            int miny = 105;
            for (int i = 1;i <= N;i++)
            {
                scanf("%d %d %d", &idx, &x, &y);
                P[idx] = point(x, y,idx);
                miny = min(miny, y);
            }
            solve(miny);
        }
    }
    

    J - Kadj Squares
    首先我们要求出所有正方形放的位置,由于题目给的正方形边长是个整数,那么它想x坐标必然是一个小数,所以这里有一个小技巧,就是把它的边长都默认乘 2 2 ,那么它的x坐标就变成整数了。
    如何求一个正方形的位置呢,我们可以枚举它之前放好的正方形,先假设它靠在这个正方形上,求出当前的x,然后找到一个最大的x就是他的位置啦。
    求完位置后在看它左边的正方形把它遮住了多少,右边的正方形把它遮住了多少,在判断一下就行了。

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<stdio.h>
    #include<vector>
    using namespace std;
    
    int B[55], L[55];
    vector<int>V;
    int main()
    {
        int n;
        while (~scanf("%d",&n)&&n)
        {
            V.clear();
            int tmp;
            for (int i = 1;i <= n;i++)
            {
                scanf("%d", &tmp);
                int x = tmp;
                L[i] = tmp;
                for (int j = 1;j < i;j++)
                {
                    if (tmp >= L[j])
                        x = max(x, B[j] + L[j] + L[j]);
                    else
                        x = max(x, B[j] + tmp * 2);
                }
                B[i] = x;
            }
    
            int ans = 0;
            for (int i = 1;i <= n;i++)
            {
                int Left=0, Right=B[i]+L[i];
                for (int j = 1;j < i;j++)
                {
                    int x = B[j] + L[j];
                    if (x >= B[i] - L[i])
                        Left = max(Left, x);
                }
                for (int j = i + 1;j <= n;j++)
                {
                    int x = B[j] - L[j];
                    if (x <= B[i] + L[i])
                        Right = min(Right, x);
                }
                if (Left < Right)V.push_back(i);
            }
            for (int i = 0;i < V.size();i++)
            {
                printf("%d", V[i]);
                if (i != V.size() - 1)printf(" ");
                else
                    puts("");
            }
            //printf("%d\n", ans);
        }
    }
    

    K - An Easy Problem?!

    一道坑题,但不得不说它是道好题。需要判断的地方很多,希望读者自行判断。。
    提一点最重要的地方,就是有可能上面的板子遮住了下面的板子,使得一点雨都就不住。
    注意精度问题,用C++交。

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<math.h>
    #include<stdio.h>
    using namespace std;
    #define eps 1e-8
    #define zero(x) (fabs(x)<eps)
    struct point 
    {
        double x, y;
        point(double sx, double sy) { x = sx;y = sy; }
        point(){}
    };
    
    struct line
    {
        point a, b;
        double ang;
        line(){}
        line(point p1, point p2)
        {
            a = p1;b = p2;
        }
        void getang()
        {
            ang = atan2((b.y - a.y) , (b.x - a.x));
        }
    };
    
    double xmult(point p1, point p2, point p0)
    {
        return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
    }
    
    int same_side(point p1, point p2, line l)
    {
        return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps;
    }
    
    int dots_inline(point p1, point p2, point p3)
    {
        return zero(xmult(p1, p2, p3));
    }
    
    int dot_online_in(point p, line l)
    {
        return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x)*(l.b.x - p.x) < eps && (l.a.y - p.y)*(l.b.y - p.y) < eps;
    }
    
    int intersect_in(line u, line v)
    {
        if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
            return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
        return dot_online_in(u.a, v) || dot_online_in(u.b, v) || dot_online_in(v.a, u) || dot_online_in(v.b, u);
    }
    
    point intersection(line u, line v)
    {
        point ret = u.a;
        double t = ((u.a.x - v.a.x)*(v.a.y - v.b.y) - (u.a.y - v.a.y)*(v.a.x - v.b.x)) / ((u.a.x - u.b.x)*(v.a.y - v.b.y) - (u.a.y - u.b.y)*(v.a.x - v.b.x));
        ret.x += (u.b.x - u.a.x)*t;
        ret.y += (u.b.y - u.a.y)*t;
        return ret;
    }
    
    double area_triangle(point p1, point p2, point p3)
    {
        return fabs(xmult(p1, p2, p3)) / 2;
    }
    
    int parallel(line u, line v)
    {
        return zero((u.a.x - u.b.x)*(v.a.y - v.b.y) - (v.a.x - v.b.x)*(u.a.y - u.b.y));
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while (T--)
        {
            double x1, y1, x2, y2, x3, y3, x4, y4;
            scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
            point p1 = point(x1, y1), p2 = point(x2, y2), p3 = point(x3, y3), p4 = point(x4, y4);
            if (p1.y < p2.y)
                swap(p1, p2);
            if (p3.y < p4.y)
                swap(p3, p4);
            if (p1.y > p3.y)
            {
                swap(p1, p3);
                swap(p2, p4);
            }
            line a = line(p1, p2);
            line b = line(p3, p4);
            a.getang();b.getang();
            if (p1.x < p2.x&&p3.x<p4.x)
            {
                if (a.ang > b.ang&&p3.x<=p1.x)
                {
                    puts("0.00");
                    continue;
                }
            }
            if (p1.x > p2.x&&p3.x > p4.x)
            {
                if (a.ang < b.ang&&p3.x>=p1.x)
                {
                    puts("0.00");
                    continue;
                }
            }
    
            if (intersect_in(a, b))
            {
    
                if (zero(a.ang - b.ang))puts("0.00");
                else
                {
                    point insec1 = intersection(a, b);
                    line c = line(p1, point(p1.x+5, p1.y));
                    if (parallel(c, b))
                        puts("0.00");
                    else
                    {
                        point insec2 = intersection(c, b);
                        printf("%.2f\n", area_triangle(insec1, insec2, p1));
                    }
                }
    
            }
            else
                puts("0.00");
        }
    
    
    }
    

    L - Pipe
    此题初看可能十分困难,但是上下顶点对于限制光线非常关键。首先,我们想到如果一根光线自始至终未曾擦到任何顶点,肯定不是最优的(可以通过平移使之优化)。然后,如果只碰到一个顶点,那也不是最优的,可以通过旋转使他碰到另一个顶点,并且更优,最后要说明,最优光线必然是擦到一个上顶点和一个下顶点。以上三步的证明用反证法并不困难。所以留给读者。
    于是有了一个简单的算法,任取一个上顶点和下顶点,形成直线l。若l能射穿左入口,即当x=x0时,直线l在(x0,y0)和(x0,y0-1)之间,则是一条可行光线。再从左到右依次判断每条上,下管壁是否与l相交,相交则求交点,并把交点x与当前最佳值比较,若所有管壁都不与l相交,说明l射穿了整个管道。(算法艺术与信息学竞赛)

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<math.h>
    #include<stdio.h>
    using namespace std;
    #define eps 1e-5
    #define zero(x) (fabs(x)<eps)
    #define inf 1e10
    
    int sgn(double x)
    {
        if (fabs(x) < eps)return 0;
        if (x < 0)return -1;
        return 1;
    }
    
    struct point
    {
        double x, y;
        point(double sx, double sy)
        {
            x = sx;
            y = sy;
        }
        point(){}
    }up[50],dwn[50];
    struct line
    {
        point a, b;
        line(point sa, point sb)
        {
            a = sa;
            b = sb;
        }
        line(){}
    }L[50];
    
    double xmult(point p1, point p2, point p0)
    {
        return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
    }
    
    int opposite_side(point p1, point p2, line l)
    {
        return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) < -eps;
    }
    
    int intersect_ex(line u, line v)
    {
        return opposite_side(u.a, u.b, v) && opposite_side(v.a, v.b, u);
    }
    
    int same_side(point p1, point p2, line l)
    {
        double tmp= xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b);
        cout << tmp << endl;
        cout << (tmp > eps) << endl;
        return tmp > eps;
    }
    
    int dots_inline(point p1, point p2, point p3)
    {
        return zero(xmult(p1, p2, p3));
    }
    
    int dot_online_in(point p, line l)
    {
        return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x)*(l.b.x - p.x) < eps && (l.a.y - p.y)*(l.b.y - p.y) < eps;
    }
    
    int intersect_in(line u, line v)
    {
        if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
            return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
        return dot_online_in(u.a, v) || dot_online_in(u.b, v) || dot_online_in(v.a, u) || dot_online_in(v.b, u);
    }
    
    int n;
    
    double dist(point a, point b)
    {
        double x = a.x - b.x;
        double y = a.y - b.y;
        return sqrt(x*x + y*y);
    }
    
    point intersection(line u, line v)
    {
        point ret = u.a;
        double t = ((u.a.x - v.a.x)*(v.a.y - v.b.y) - (u.a.y - v.a.y)*(v.a.x - v.b.x)) / ((u.a.x - u.b.x)*(v.a.y - v.b.y) - (u.a.y - u.b.y)*(v.a.x - v.b.x));
        ret.x += (u.b.x - u.a.x)*t;
        ret.y += (u.b.y - u.a.y)*t;
        return ret;
    }
    
    int Seg_inter_line(line l1, line l2)//判断直线l1和线段l2是否相交
    {
        double tmp1 = xmult(l2.a, l1.a, l1.b);
        double tmp2 = xmult(l2.b, l1.a, l1.b);
        return sgn(tmp1)*sgn(tmp2) <= 0;
    }
    
    void solve()
    {
        line first = line(up[1], dwn[1]);
        double ans = -inf;
        for(int i=1;i<=n;i++)
            for (int j = 1;j <= n;j++)
            {
                line it = line(up[i], dwn[j]); 
                if (Seg_inter_line(it,first))
                {
                    for (int k = 1;k <= n;k++)
                    {
                        line now = line(up[k], dwn[k]);
                        if (!Seg_inter_line(it, now))
                        {
                            line tmp1 = line(up[k], up[k - 1]);
                            line tmp2 = line(dwn[k], dwn[k - 1]);
                            if (Seg_inter_line(it, tmp1))
                            {
                                point t = intersection(it, tmp1);
                                ans = max(ans, t.x);
                            }
                            if (Seg_inter_line(it, tmp2))
                            {
                                point t = intersection(it, tmp2);
                                ans = max(ans, t.x);
                            }
                            break;
                        }
                        if (k == n)
                        {
                            ans = up[n].x + 1;
                        }
                    }
    
    
                }
            }
        if (zero(ans - up[n].x-1))
            puts("Through all the pipe.");
        else
            printf("%.2f\n", ans);
    
    }
    
    int main()
    {
        while (~scanf("%d",&n)&&n)
        {
            double x, y;
            for (int i = 1;i <= n;i++)
            {
                scanf("%lf %lf", &x, &y);
                up[i] = point(x, y);
                dwn[i] = point(x, y - 1);
            }
            solve();
        }
    }

    M - Geometric Shapes
    本专题最傻的题。本来不想贴的,但感觉代码写的太好了,所以贴上来。。

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<stdio.h>
    #include<vector>
    #include<string>
    #include<math.h>
    using namespace std;
    #define eps 1e-5
    #define zero(x) (fabs(x)<eps)
    const double pi = acos(-1);
    struct point
    {
        double x, y;
        point(double sa, double sb)
        {
            x = sa;
            y = sb;
        }
        point() {}
        bool operator<(const point &b)const
        {
            if (x != b.x)
                return x < b.x;
            return y < b.y;
        }
    };
    
    struct line
    {
        char s;
        point a, b;
        line(point sa, point sb, char ss)
        {
            a = sa;
            b = sb;
            s = ss;
        }
        line() {}
    };
    line L[1000];
    int lcnt;
    
    point rotate(point v, point p, double angle)
    {
        point ret = p;
        v.x -= p.x, v.y -= p.y;
        p.x = cos(angle);
        p.y = sin(angle);
        ret.x += v.x*p.x - v.y*p.y;
        ret.y += v.x*p.y + v.y*p.x;
        return ret;
    }
    
    void reads(char s)
    {
        char tmp1[50], tmp2[50];
        scanf("%s %s", tmp1, tmp2);
        int x1, y1, x2, y2;
        sscanf(tmp1, "(%d,%d)", &x1, &y1);
        sscanf(tmp2, "(%d,%d)", &x2, &y2);
        point p1 = point(x1, y1);
        point p2 = point(x2, y2);
        point p3, p4;
        point mid = point((x1 + x2 + 0.0) / 2.0, (y1 + y2 + 0.0) / 2.0);
        p3 = rotate(p1, mid, pi / 2);
        p4 = rotate(p1, mid, -pi / 2);
    
        L[++lcnt] = line(p1, p3, s);
        L[++lcnt] = line(p1, p4, s);
        L[++lcnt] = line(p2, p3, s);
        L[++lcnt] = line(p2, p4, s);
    }
    
    void readr(char s)
    {
        char tmp1[50], tmp2[50], tmp3[50];
        scanf("%s %s %s", tmp1, tmp2, tmp3);
        int x1, y1, x2, y2, x3, y3;
        sscanf(tmp1, "(%d,%d)", &x1, &y1);
        sscanf(tmp2, "(%d,%d)", &x2, &y2);
        sscanf(tmp3, "(%d,%d)", &x3, &y3);
        point p[4];
        p[0] = point(x1, y1);
        p[1] = point(x2, y2);
        p[2] = point(x3, y3);
    
        p[3] = point(p[2].x + (p[0].x - p[1].x), p[2].y - (p[1].y - p[0].y));
        L[++lcnt] = line(p[0], p[1], s);
        L[++lcnt] = line(p[1], p[2], s);
        L[++lcnt] = line(p[2], p[3], s);
        L[++lcnt] = line(p[0], p[3], s);
    }
    
    void readl(char s)
    {
        char tmp1[50], tmp2[50];
        scanf("%s %s", tmp1, tmp2);
        int x1, y1, x2, y2;
        sscanf(tmp1, "(%d,%d)", &x1, &y1);
        sscanf(tmp2, "(%d,%d)", &x2, &y2);
        point a = point(x1, y1);
        point b = point(x2, y2);
        L[++lcnt] = line(a, b,s);
    }
    
    void readt(char s)
    {
        char tmp1[50], tmp2[50], tmp3[50];
        scanf("%s %s %s", tmp1, tmp2, tmp3);
        int x1, y1, x2, y2, x3, y3;
        sscanf(tmp1, "(%d,%d)", &x1, &y1);
        sscanf(tmp2, "(%d,%d)", &x2, &y2);
        sscanf(tmp3, "(%d,%d)", &x3, &y3);
        point a = point(x1, y1);
        point b = point(x2, y2);
        point c = point(x3, y3);
        L[++lcnt] = line(a, b,s);
        L[++lcnt] = line(a, c,s);
        L[++lcnt] = line(b, c,s);
    }
    
    void readp(char s)
    {
        int num;
        scanf("%d", &num);
        int x1, y1;
        char tmp1[50];
        scanf("%s", tmp1);
        sscanf(tmp1, "(%d,%d)", &x1, &y1);
        int beforex = x1, beforey = y1;
        int nowx, nowy;
        for (int i = 2;i <= num;i++)
        {
            scanf("%s", tmp1);
            sscanf(tmp1, "(%d,%d)", &nowx, &nowy);
            L[++lcnt] = line(point(beforex, beforey), point(nowx, nowy),s);
            beforex = nowx;
            beforey = nowy;
        }
        L[++lcnt] = line(point(x1, y1), point(nowx, nowy), s);
    }
    bool col[30][30];
    bool have[30];
    bool read(char s, bool change)
    {
        if (change)
        {
            lcnt = 0;
            memset(col, 0, sizeof(col));
            memset(have, 0, sizeof(have));
        }
    
        char str[5];
        scanf("%s", str);
        if (str[0] == s)return 0;
        have[str[0] - 'A'] = 1;
        string type;
        cin >> type;
        if (type[0] == 's')
            reads(str[0]);
        else if (type[0] == 'r')
            readr(str[0]);
        else if (type[0] == 'l')
            readl(str[0]);
        else if (type[0] == 't')
            readt(str[0]);
        else if (type[0] == 'p')
            readp(str[0]);
        return 1;
    }
    
    double xmult(point p1, point p2, point p0)
    {
        return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
    }
    
    int dots_inline(point p1, point p2, point p3)
    {
        return zero(xmult(p1, p2, p3));
    }
    
    int same_side(point p1, point p2, line l)
    {
        return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps;
    }
    
    int dot_online_in(point p, line l)
    {
        return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x)*(l.b.x - p.x) < eps && (l.a.y - p.y)*(l.b.y - p.y) < eps;
    }
    
    int intersect_in(line u, line v)
    {
        if (!dots_inline(u.a, u.b, v.a) || !dots_inline(u.a, u.b, v.b))
            return !same_side(u.a, u.b, v) && !same_side(v.a, v.b, u);
        return dot_online_in(u.a, v) || dot_online_in(u.b, v) || dot_online_in(v.a, u) || dot_online_in(v.b, u);
    }
    
    int check(int num,int &flag)
    {
        int cnt = 0;
        for (int i = 0;i < 26;i++)if (col[num][i])cnt++;
        if (cnt == 1)
            flag = 1;
        else if (cnt == 2)
            flag = 2;
        else flag = 3;
        for (int i = 25;i >= 0;i--)if (col[num][i])
            return i;
        return -1;
    }
    
    void solve()
    {
        for(int i=1;i<=lcnt;i++)
            for (int j = i + 1;j <= lcnt;j++)if(L[i].s!=L[j].s)
            {
                if (intersect_in(L[i], L[j]))
                {
                    col[L[i].s-'A'][L[j].s-'A'] = col[L[j].s-'A'][L[i].s-'A'] = 1;
                }
            }
        for (int i = 0;i < 26;i++)if (have[i])
        {
            printf("%c", 'A' + i);
            int flag;
            int last = check(i,flag);
            if (last==-1)
                puts(" has no intersections");
            else
            {
                printf(" intersects with");
                if (flag == 1)
                {
                    printf(" %c\n", last + 'A');
                }
                else if (flag == 2)
                {
                    for (int j = 0;j <= last;j++)
                    {
                        if (!col[i][j])
                            continue;
                        char tmp = j + 'A';
                        if (j != last)
                            printf(" %c", tmp);
                        else
                            printf(" and %c\n", tmp);
                    }
                }
                else
                {
                    for (int j = 0;j <= last;j++)
                    {
                        if (!col[i][j])
                            continue;
                        char tmp = j + 'A';
                        if (j != last)
                            printf(" %c,", tmp);
                        else
                            printf(" and %c\n", tmp);
                    }
                }
            }
        }
    
    }
    
    int main()
    {
        string name;
        while (read('.', true))
        {
            while (read('-', false));
            solve();
            puts("");
        }
    
    
    }
    

    N - A Round Peg in a Ground Hole
    一道模板题。先用叉积判断是不是凸包,再判断圆心是否在多边形内部,再用距离判断多边形是否把圆包围。

    #include<stdio.h>
    #include<math.h>
    #include<algorithm>
    using namespace std;
    
    const int MAXN = 1e3 + 7;
    const double EPS = 1e-8;
    const double oo = 1e10 + 7;
    
    struct Point
    {
        double x, y;
        Point(double x = 0, double y = 0) :x(x), y(y) {}
        Point operator - (const Point &tmp)const {
            return Point(x - tmp.x, y - tmp.y);
        }
        double operator ^(const Point &tmp)const {
            return x*tmp.y - y*tmp.x;
        }
        double operator *(const Point &tmp)const {
            return x*tmp.x + y*tmp.y;
        }
    };
    double Dist(Point a, Point b)
    {///两点间的距离
        return sqrt((a - b)*(a - b));
    }
    int Sign(double t)
    {
        if (t > EPS)return 1;
        if (fabs(t) < EPS)return 0;
        return -1;///负数
    }
    struct Segment
    {
        Point S, E;
        Segment(Point S = 0, Point E = 0) :S(S), E(E) {}
        bool OnSeg(const Point &p)
        {///点是否在线段上
            if (Sign((S - E) ^ (p - E)) == 0)///共线
                if (Sign((p.x - S.x)*(p.x - E.x)) <= 0)///位于线段的中间或者端点
                    if (Sign((p.y - S.y)*(p.y - E.y)) <= 0)
                        return true;
            return false;
        }
        bool Inter(const Segment &tmp)
        {///只考虑完全相交的情况
            return Sign((S - E) ^ (tmp.S - E)) * Sign((S - E) ^ (tmp.E - E)) == -1;
        }
        Point NearPoint(const Point &p)
        {///点到线段最近的点
            Point res;
            double r = ((E - S)*(p - S)) / ((E - S)*(E - S));
    
            if (r > EPS && (1.0 - r) > EPS)
            {///点在线段的投影在线段上
                res.x = S.x + r * (E.x - S.x);
                res.y = S.y + r * (E.y - S.y);
            }
            else
            {///求离最近的端点
                if (Dist(p, S) < Dist(p, E))
                    res = S;
                else
                    res = E;
            }
    
            return res;
        }
    };
    struct Poly
    {
        int N;
        Point vertex[MAXN];
    
        bool IsConvex()
        {///判断是否是凸多边形,可以共线
            int vis[3] = { 0 };
            for (int i = 0; i<N; i++)
            {///如果同时出现整数和负数,说明存在凹的
                int k = Sign((vertex[(i + 1) % N] - vertex[i]) ^ (vertex[(i + 2) % N] - vertex[i]));
                vis[k + 1] = 1;
    
                if (vis[0] && vis[2])
                    return false;
            }
            return true;
        }
        int InPoly(const Point &Q)
        {///判断点Q是否在多边形内,射线法,奇数在内,偶数在外
         ///在圆上返回0, 圆外-1, 圆内 1
            Segment ray(Point(-oo, Q.y), Q);///构造射线的最远处
            int cnt = 0;///统计相交的边数
    
            for (int i = 0; i<N; i++)
            {
                Segment edge(vertex[i], vertex[(i + 1) % N]);
    
                if (edge.OnSeg(Q) == true)
                    return 0;///点在边上
    
                if (ray.OnSeg(vertex[i]) == true)
                {///如果相交连接点,那么取y值小的点
                    if (vertex[(i + 1) % N].y - vertex[i].y > EPS)
                        cnt++;
                }
                else if (ray.OnSeg(vertex[(i + 1) % N]) == true)
                {
                    if (vertex[i].y - vertex[(i + 1) % N].y > EPS)
                        cnt++;
                }
                else if (ray.Inter(edge) && edge.Inter(ray))
                    cnt++;
            }
    
            if (cnt % 2)
                return 1;
            else
                return -1;
        }
    };
    struct Circle
    {
        Point center;///圆心
        double R;///半径
    };
    
    bool Find(Poly &a, Circle &c)
    {///判断圆是否在多边形内
        if (a.InPoly(c.center) == -1)
            return false;///如果圆心在多边形外面
    
        for (int i = 0; i<a.N; i++)
        {
            Segment edge(a.vertex[i], a.vertex[(i + 1) % a.N]);
            double len = Dist(c.center, edge.NearPoint(c.center));
    
            if (Sign(len - c.R) < 0)
                return false;
        }
    
        return true;
    }
    
    int main()
    {
        Poly a;///定义多边形
        Circle c;///定义圆
    
        while (scanf("%d", &a.N) != EOF && a.N > 2)
        {
            scanf("%lf%lf%lf", &c.R, &c.center.x, &c.center.y);
            for (int i = 0; i<a.N; i++)
                scanf("%lf%lf", &a.vertex[i].x, &a.vertex[i].y);
    
            if (a.IsConvex() == false)
                printf("HOLE IS ILL-FORMED\n");
            else if (Find(a, c) == false)
                printf("PEG WILL NOT FIT\n");
            else
                printf("PEG WILL FIT\n");
        }
    
        return 0;
    }
    

    之后会把整理的模板贴上来。

    展开全文
  • // `计算几何模板` const double eps = 1e-8; const double inf = 1e20; const double pi = acos(-1.0); const int maxp = 1010; //`Compares a double to zero` int sgn(double x){ if(fabs(x) <...

    二维几何部分

    // `计算几何模板`
    const double eps = 1e-8;
    const double inf = 1e20;
    const double pi = acos(-1.0);
    const int maxp = 1010;
    //`Compares a double to zero`
    int sgn(double x){
        if(fabs(x) < eps)return 0;
        if(x < 0)return -1;
        else return 1;
    }
    //square of a double
    inline double sqr(double x){return x*x;}
    /*
     * Point
     * Point()               - Empty constructor
     * Point(double _x,double _y)  - constructor
     * input()             - double input
     * output()            - %.2f output
     * operator ==         - compares x and y
     * operator <          - compares first by x, then by y
     * operator -          - return new Point after subtracting curresponging x and y
     * operator ^          - cross product of 2d points
     * operator *          - dot product
     * len()               - gives length from origin
     * len2()              - gives square of length from origin
     * distance(Point p)   - gives distance from p
     * operator + Point b  - returns new Point after adding curresponging x and y
     * operator * double k - returns new Point after multiplieing x and y by k
     * operator / double k - returns new Point after divideing x and y by k
     * rad(Point a,Point b)- returns the angle of Point a and Point b from this Point
     * trunc(double r)     - return Point that if truncated the distance from center to r
     * rotleft()           - returns 90 degree ccw rotated point
     * rotright()          - returns 90 degree cw rotated point
     * rotate(Point p,double angle) - returns Point after rotateing the Point centering at p by angle radian ccw
     */
    struct Point{
        double x,y;
        Point(){}
        Point(double _x,double _y){
            x = _x;
            y = _y;
        }
        void input(){
            scanf("%lf%lf",&x,&y);
        }
        void output(){
            printf("%.2f %.2f\n",x,y);
        }
        bool operator == (Point b)const{
            return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
        }
        bool operator < (Point b)const{
            return sgn(x-b.x)== 0?sgn(y-b.y)<0:x<b.x;
        }
        Point operator -(const Point &b)const{
            return Point(x-b.x,y-b.y);
        }
        //叉积
        double operator ^(const Point &b)const{
            return x*b.y - y*b.x;
        }
        //点积
        double operator *(const Point &b)const{
            return x*b.x + y*b.y;
        }
        //返回长度
        double len(){
            return hypot(x,y);//库函数
        }
        //返回长度的平方
        double len2(){
            return x*x + y*y;
        }
        //返回两点的距离
        double distance(Point p){
            return hypot(x-p.x,y-p.y);
        }
        Point operator +(const Point &b)const{
            return Point(x+b.x,y+b.y);
        }
        Point operator *(const double &k)const{
            return Point(x*k,y*k);
        }
        Point operator /(const double &k)const{
            return Point(x/k,y/k);
        }
        //`计算pa  和  pb 的夹角`
        //`就是求这个点看a,b 所成的夹角`
        //`测试 LightOJ1203`
        double rad(Point a,Point b){
            Point p = *this;
            return fabs(atan2( fabs((a-p)^(b-p)),(a-p)*(b-p) ));
        }
        //`化为长度为r的向量`
        Point trunc(double r){
            double l = len();
            if(!sgn(l))return *this;
            r /= l;
            return Point(x*r,y*r);
        }
        //`逆时针旋转90度`
        Point rotleft(){
            return Point(-y,x);
        }
        //`顺时针旋转90度`
        Point rotright(){
            return Point(y,-x);
        }
        //`绕着p点逆时针旋转angle`
        Point rotate(Point p,double angle){
            Point v = (*this) - p;
            double c = cos(angle), s = sin(angle);
            return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c);
        }
    };
    /*
     * Stores two points
     * Line()                         - Empty constructor
     * Line(Point _s,Point _e)        - Line through _s and _e
     * operator ==                    - checks if two points are same
     * Line(Point p,double angle)     - one end p , another end at angle degree
     * Line(double a,double b,double c) - Line of equation ax + by + c = 0
     * input()                        - inputs s and e
     * adjust()                       - orders in such a way that s < e
     * length()                       - distance of se
     * angle()                        - return 0 <= angle < pi
     * relation(Point p)              - 3 if point is on line
     *                                  1 if point on the left of line
     *                                  2 if point on the right of line
     * pointonseg(double p)           - return true if point on segment
     * parallel(Line v)               - return true if they are parallel
     * segcrossseg(Line v)            - returns 0 if does not intersect
     *                                  returns 1 if non-standard intersection
     *                                  returns 2 if intersects
     * linecrossseg(Line v)           - line and seg
     * linecrossline(Line v)          - 0 if parallel
     *                                  1 if coincides
     *                                  2 if intersects
     * crosspoint(Line v)             - returns intersection point
     * dispointtoline(Point p)        - distance from point p to the line
     * dispointtoseg(Point p)         - distance from p to the segment
     * dissegtoseg(Line v)            - distance of two segment
     * lineprog(Point p)              - returns projected point p on se line
     * symmetrypoint(Point p)         - returns reflection point of p over se
     *
     */
    struct Line{
        Point s,e;
        Line(){}
        Line(Point _s,Point _e){
            s = _s;
            e = _e;
        }
        bool operator ==(Line v){
            return (s == v.s)&&(e == v.e);
        }
        //`根据一个点和倾斜角angle确定直线,0<=angle<pi`
        Line(Point p,double angle){
            s = p;
            if(sgn(angle-pi/2) == 0){
                e = (s + Point(0,1));
            }
            else{
                e = (s + Point(1,tan(angle)));
            }
        }
        //ax+by+c=0
        Line(double a,double b,double c){
            if(sgn(a) == 0){
                s = Point(0,-c/b);
                e = Point(1,-c/b);
            }
            else if(sgn(b) == 0){
                s = Point(-c/a,0);
                e = Point(-c/a,1);
            }
            else{
                s = Point(0,-c/b);
                e = Point(1,(-c-a)/b);
            }
        }
        void input(){
            s.input();
            e.input();
        }
        void adjust(){
            if(e < s)swap(s,e);
        }
        //求线段长度
        double length(){
            return s.distance(e);
        }
        //`返回直线倾斜角 0<=angle<pi`
        double angle(){
            double k = atan2(e.y-s.y,e.x-s.x);
            if(sgn(k) < 0)k += pi;
            if(sgn(k-pi) == 0)k -= pi;
            return k;
        }
        //`点和直线关系`
        //`1  在左侧`
        //`2  在右侧`
        //`3  在直线上`
        int relation(Point p){
            int c = sgn((p-s)^(e-s));
            if(c < 0)return 1;
            else if(c > 0)return 2;
            else return 3;
        }
        // 点在线段上的判断
        bool pointonseg(Point p){
            return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;
        }
        //`两向量平行(对应直线平行或重合)`
        bool parallel(Line v){
            return sgn((e-s)^(v.e-v.s)) == 0;
        }
        //`两线段相交判断`
        //`2 规范相交`
        //`1 非规范相交`
        //`0 不相交`
        int segcrossseg(Line v){
            int d1 = sgn((e-s)^(v.s-s));
            int d2 = sgn((e-s)^(v.e-s));
            int d3 = sgn((v.e-v.s)^(s-v.s));
            int d4 = sgn((v.e-v.s)^(e-v.s));
            if( (d1^d2)==-2 && (d3^d4)==-2 )return 2;
            return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||
                (d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||
                (d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||
                (d4==0 && sgn((e-v.s)*(e-v.e))<=0);
        }
        //`直线和线段相交判断`
        //`-*this line   -v seg`
        //`2 规范相交`
        //`1 非规范相交`
        //`0 不相交`
        int linecrossseg(Line v){
            int d1 = sgn((e-s)^(v.s-s));
            int d2 = sgn((e-s)^(v.e-s));
            if((d1^d2)==-2) return 2;
            return (d1==0||d2==0);
        }
        //`两直线关系`
        //`0 平行`
        //`1 重合`
        //`2 相交`
        int linecrossline(Line v){
            if((*this).parallel(v))
                return v.relation(s)==3;
            return 2;
        }
        //`求两直线的交点`
        //`要保证两直线不平行或重合`
        Point crosspoint(Line v){
            double a1 = (v.e-v.s)^(s-v.s);
            double a2 = (v.e-v.s)^(e-v.s);
            return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
        }
        //点到直线的距离
        double dispointtoline(Point p){
            return fabs((p-s)^(e-s))/length();
        }
        //点到线段的距离
        double dispointtoseg(Point p){
            if(sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0)
                return min(p.distance(s),p.distance(e));
            return dispointtoline(p);
        }
        //`返回线段到线段的距离`
        //`前提是两线段不相交,相交距离就是0了`
        double dissegtoseg(Line v){
            return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));
        }
        //`返回点p在直线上的投影`
        Point lineprog(Point p){
            return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
        }
        //`返回点p关于直线的对称点`
        Point symmetrypoint(Point p){
            Point q = lineprog(p);
            return Point(2*q.x-p.x,2*q.y-p.y);
        }
    };
    //
    struct circle{
        Point p;//圆心
        double r;//半径
        circle(){}
        circle(Point _p,double _r){
            p = _p;
            r = _r;
        }
        circle(double x,double y,double _r){
            p = Point(x,y);
            r = _r;
        }
        //`三角形的外接圆`
        //`需要Point的+ /  rotate()  以及Line的crosspoint()`
        //`利用两条边的中垂线得到圆心`
        //`测试:UVA12304`
        circle(Point a,Point b,Point c){
            Line u = Line((a+b)/2,((a+b)/2)+((b-a).rotleft()));
            Line v = Line((b+c)/2,((b+c)/2)+((c-b).rotleft()));
            p = u.crosspoint(v);
            r = p.distance(a);
        }
        //`三角形的内切圆`
        //`参数bool t没有作用,只是为了和上面外接圆函数区别`
        //`测试:UVA12304`
        circle(Point a,Point b,Point c,bool t){
            Line u,v;
            double m = atan2(b.y-a.y,b.x-a.x), n = atan2(c.y-a.y,c.x-a.x);
            u.s = a;
            u.e = u.s + Point(cos((n+m)/2),sin((n+m)/2));
            v.s = b;
            m = atan2(a.y-b.y,a.x-b.x) , n = atan2(c.y-b.y,c.x-b.x);
            v.e = v.s + Point(cos((n+m)/2),sin((n+m)/2));
            p = u.crosspoint(v);
            r = Line(a,b).dispointtoseg(p);
        }
        //输入
        void input(){
            p.input();
            scanf("%lf",&r);
        }
        //输出
        void output(){
            printf("%.2lf %.2lf %.2lf\n",p.x,p.y,r);
        }
        bool operator == (circle v){
            return (p==v.p) && sgn(r-v.r)==0;
        }
        bool operator < (circle v)const{
            return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));
        }
        //面积
        double area(){
            return pi*r*r;
        }
        //周长
        double circumference(){
            return 2*pi*r;
        }
        //`点和圆的关系`
        //`0 圆外`
        //`1 圆上`
        //`2 圆内`
        int relation(Point b){
            double dst = b.distance(p);
            if(sgn(dst-r) < 0)return 2;
            else if(sgn(dst-r)==0)return 1;
            return 0;
        }
        //`线段和圆的关系`
        //`比较的是圆心到线段的距离和半径的关系`
        int relationseg(Line v){
            double dst = v.dispointtoseg(p);
            if(sgn(dst-r) < 0)return 2;
            else if(sgn(dst-r) == 0)return 1;
            return 0;
        }
        //`直线和圆的关系`
        //`比较的是圆心到直线的距离和半径的关系`
        int relationline(Line v){
            double dst = v.dispointtoline(p);
            if(sgn(dst-r) < 0)return 2;
            else if(sgn(dst-r) == 0)return 1;
            return 0;
        }
        //`两圆的关系`
        //`5 相离`
        //`4 外切`
        //`3 相交`
        //`2 内切`
        //`1 内含`
        //`需要Point的distance`
        //`测试:UVA12304`
        int relationcircle(circle v){
            double d = p.distance(v.p);
            if(sgn(d-r-v.r) > 0)return 5;
            if(sgn(d-r-v.r) == 0)return 4;
            double l = fabs(r-v.r);
            if(sgn(d-r-v.r)<0 && sgn(d-l)>0)return 3;
            if(sgn(d-l)==0)return 2;
            if(sgn(d-l)<0)return 1;
        }
        //`求两个圆的交点,返回0表示没有交点,返回1是一个交点,2是两个交点`
        //`需要relationcircle`
        //`测试:UVA12304`
        int pointcrosscircle(circle v,Point &p1,Point &p2){
            int rel = relationcircle(v);
            if(rel == 1 || rel == 5)return 0;
            double d = p.distance(v.p);
            double l = (d*d+r*r-v.r*v.r)/(2*d);
            double h = sqrt(r*r-l*l);
            Point tmp = p + (v.p-p).trunc(l);
            p1 = tmp + ((v.p-p).rotleft().trunc(h));
            p2 = tmp + ((v.p-p).rotright().trunc(h));
            if(rel == 2 || rel == 4)
                return 1;
            return 2;
        }
        //`求直线和圆的交点,返回交点个数`
        int pointcrossline(Line v,Point &p1,Point &p2){
            if(!(*this).relationline(v))return 0;
            Point a = v.lineprog(p);
            double d = v.dispointtoline(p);
            d = sqrt(r*r-d*d);
            if(sgn(d) == 0){
                p1 = a;
                p2 = a;
                return 1;
            }
            p1 = a + (v.e-v.s).trunc(d);
            p2 = a - (v.e-v.s).trunc(d);
            return 2;
        }
        //`得到过a,b两点,半径为r1的两个圆`
        int gercircle(Point a,Point b,double r1,circle &c1,circle &c2){
            circle x(a,r1),y(b,r1);
            int t = x.pointcrosscircle(y,c1.p,c2.p);
            if(!t)return 0;
            c1.r = c2.r = r;
            return t;
        }
        //`得到与直线u相切,过点q,半径为r1的圆`
        //`测试:UVA12304`
        int getcircle(Line u,Point q,double r1,circle &c1,circle &c2){
            double dis = u.dispointtoline(q);
            if(sgn(dis-r1*2)>0)return 0;
            if(sgn(dis) == 0){
                c1.p = q + ((u.e-u.s).rotleft().trunc(r1));
                c2.p = q + ((u.e-u.s).rotright().trunc(r1));
                c1.r = c2.r = r1;
                return 2;
            }
            Line u1 = Line((u.s + (u.e-u.s).rotleft().trunc(r1)),(u.e + (u.e-u.s).rotleft().trunc(r1)));
            Line u2 = Line((u.s + (u.e-u.s).rotright().trunc(r1)),(u.e + (u.e-u.s).rotright().trunc(r1)));
            circle cc = circle(q,r1);
            Point p1,p2;
            if(!cc.pointcrossline(u1,p1,p2))cc.pointcrossline(u2,p1,p2);
            c1 = circle(p1,r1);
            if(p1 == p2){
                c2 = c1;
                return 1;
            }
            c2 = circle(p2,r1);
            return 2;
        }
        //`同时与直线u,v相切,半径为r1的圆`
        //`测试:UVA12304`
        int getcircle(Line u,Line v,double r1,circle &c1,circle &c2,circle &c3,circle &c4){
            if(u.parallel(v))return 0;//两直线平行
            Line u1 = Line(u.s + (u.e-u.s).rotleft().trunc(r1),u.e + (u.e-u.s).rotleft().trunc(r1));
            Line u2 = Line(u.s + (u.e-u.s).rotright().trunc(r1),u.e + (u.e-u.s).rotright().trunc(r1));
            Line v1 = Line(v.s + (v.e-v.s).rotleft().trunc(r1),v.e + (v.e-v.s).rotleft().trunc(r1));
            Line v2 = Line(v.s + (v.e-v.s).rotright().trunc(r1),v.e + (v.e-v.s).rotright().trunc(r1));
            c1.r = c2.r = c3.r = c4.r = r1;
            c1.p = u1.crosspoint(v1);
            c2.p = u1.crosspoint(v2);
            c3.p = u2.crosspoint(v1);
            c4.p = u2.crosspoint(v2);
            return 4;
        }
        //`同时与不相交圆cx,cy相切,半径为r1的圆`
        //`测试:UVA12304`
        int getcircle(circle cx,circle cy,double r1,circle &c1,circle &c2){
            circle x(cx.p,r1+cx.r),y(cy.p,r1+cy.r);
            int t = x.pointcrosscircle(y,c1.p,c2.p);
            if(!t)return 0;
            c1.r = c2.r = r1;
            return t;
        }
    
        //`过一点作圆的切线(先判断点和圆的关系)`
        //`测试:UVA12304`
        int tangentline(Point q,Line &u,Line &v){
            int x = relation(q);
            if(x == 2)return 0;
            if(x == 1){
                u = Line(q,q + (q-p).rotleft());
                v = u;
                return 1;
            }
            double d = p.distance(q);
            double l = r*r/d;
            double h = sqrt(r*r-l*l);
            u = Line(q,p + ((q-p).trunc(l) + (q-p).rotleft().trunc(h)));
            v = Line(q,p + ((q-p).trunc(l) + (q-p).rotright().trunc(h)));
            return 2;
        }
        //`求两圆相交的面积`
        double areacircle(circle v){
            int rel = relationcircle(v);
            if(rel >= 4)return 0.0;
            if(rel <= 2)return min(area(),v.area());
            double d = p.distance(v.p);
            double hf = (r+v.r+d)/2.0;
            double ss = 2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
            double a1 = acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
            a1 = a1*r*r;
            double a2 = acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
            a2 = a2*v.r*v.r;
            return a1+a2-ss;
        }
        //`求圆和三角形pab的相交面积`
        //`测试:POJ3675 HDU3982 HDU2892`
        double areatriangle(Point a,Point b){
            if(sgn((p-a)^(p-b)) == 0)return 0.0;
            Point q[5];
            int len = 0;
            q[len++] = a;
            Line l(a,b);
            Point p1,p2;
            if(pointcrossline(l,q[1],q[2])==2){
                if(sgn((a-q[1])*(b-q[1]))<0)q[len++] = q[1];
                if(sgn((a-q[2])*(b-q[2]))<0)q[len++] = q[2];
            }
            q[len++] = b;
            if(len == 4 && sgn((q[0]-q[1])*(q[2]-q[1]))>0)swap(q[1],q[2]);
            double res = 0;
            for(int i = 0;i < len-1;i++){
                if(relation(q[i])==0||relation(q[i+1])==0){
                    double arg = p.rad(q[i],q[i+1]);
                    res += r*r*arg/2.0;
                }
                else{
                    res += fabs((q[i]-p)^(q[i+1]-p))/2.0;
                }
            }
            return res;
        }
    };
    
    /*
     * n,p  Line l for each side
     * input(int _n)                        - inputs _n size polygon
     * add(Point q)                         - adds a point at end of the list
     * getline()                            - populates line array
     * cmp                                  - comparision in convex_hull order
     * norm()                               - sorting in convex_hull order
     * getconvex(polygon &convex)           - returns convex hull in convex
     * Graham(polygon &convex)              - returns convex hull in convex
     * isconvex()                           - checks if convex
     * relationpoint(Point q)               - returns 3 if q is a vertex
     *                                                2 if on a side
     *                                                1 if inside
     *                                                0 if outside
     * convexcut(Line u,polygon &po)        - left side of u in po
     * gercircumference()                   - returns side length
     * getarea()                            - returns area
     * getdir()                             - returns 0 for cw, 1 for ccw
     * getbarycentre()                      - returns barycenter
     *
     */
    struct polygon{
        int n;
        Point p[maxp];
        Line l[maxp];
        void input(int _n){
            n = _n;
            for(int i = 0;i < n;i++)
                p[i].input();
        }
        void add(Point q){
            p[n++] = q;
        }
        void getline(){
            for(int i = 0;i < n;i++){
                l[i] = Line(p[i],p[(i+1)%n]);
            }
        }
        struct cmp{
            Point p;
            cmp(const Point &p0){p = p0;}
            bool operator()(const Point &aa,const Point &bb){
                Point a = aa, b = bb;
                int d = sgn((a-p)^(b-p));
                if(d == 0){
                    return sgn(a.distance(p)-b.distance(p)) < 0;
                }
                return d > 0;
            }
        };
        //`进行极角排序`
        //`首先需要找到最左下角的点`
        //`需要重载号好Point的 < 操作符(min函数要用) `
        void norm(){
            Point mi = p[0];
            for(int i = 1;i < n;i++)mi = min(mi,p[i]);
            sort(p,p+n,cmp(mi));
        }
        //`得到凸包`
        //`得到的凸包里面的点编号是0$\sim$n-1的`
        //`两种凸包的方法`
        //`注意如果有影响,要特判下所有点共点,或者共线的特殊情况`
        //`测试 LightOJ1203  LightOJ1239`
        void getconvex(polygon &convex){
            sort(p,p+n);
            convex.n = n;
            for(int i = 0;i < min(n,2);i++){
                convex.p[i] = p[i];
            }
            if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
            if(n <= 2)return;
            int &top = convex.n;
            top = 1;
            for(int i = 2;i < n;i++){
                while(top && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)
                    top--;
                convex.p[++top] = p[i];
            }
            int temp = top;
            convex.p[++top] = p[n-2];
            for(int i = n-3;i >= 0;i--){
                while(top != temp && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)
                    top--;
                convex.p[++top] = p[i];
            }
            if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
            convex.norm();//`原来得到的是顺时针的点,排序后逆时针`
        }
        //`得到凸包的另外一种方法`
        //`测试 LightOJ1203  LightOJ1239`
        void Graham(polygon &convex){
            norm();
            int &top = convex.n;
            top = 0;
            if(n == 1){
                top = 1;
                convex.p[0] = p[0];
                return;
            }
            if(n == 2){
                top = 2;
                convex.p[0] = p[0];
                convex.p[1] = p[1];
                if(convex.p[0] == convex.p[1])top--;
                return;
            }
            convex.p[0] = p[0];
            convex.p[1] = p[1];
            top = 2;
            for(int i = 2;i < n;i++){
                while( top > 1 && sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2])) <= 0 )
                    top--;
                convex.p[top++] = p[i];
            }
            if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判
        }
        //`判断是不是凸的`
        bool isconvex(){
            bool s[2];
            memset(s,false,sizeof(s));
            for(int i = 0;i < n;i++){
                int j = (i+1)%n;
                int k = (j+1)%n;
                s[sgn((p[j]-p[i])^(p[k]-p[i]))+1] = true;
                if(s[0] && s[2])return false;
            }
            return true;
        }
        //`判断点和任意多边形的关系`
        //` 3 点上`
        //` 2 边上`
        //` 1 内部`
        //` 0 外部`
        int relationpoint(Point q){
            for(int i = 0;i < n;i++){
                if(p[i] == q)return 3;
            }
            getline();
            for(int i = 0;i < n;i++){
                if(l[i].pointonseg(q))return 2;
            }
            int cnt = 0;
            for(int i = 0;i < n;i++){
                int j = (i+1)%n;
                int k = sgn((q-p[j])^(p[i]-p[j]));
                int u = sgn(p[i].y-q.y);
                int v = sgn(p[j].y-q.y);
                if(k > 0 && u < 0 && v >= 0)cnt++;
                if(k < 0 && v < 0 && u >= 0)cnt--;
            }
            return cnt != 0;
        }
        //`直线u切割凸多边形左侧`
        //`注意直线方向`
        //`测试:HDU3982`
        void convexcut(Line u,polygon &po){
            int &top = po.n;//注意引用
            top = 0;
            for(int i = 0;i < n;i++){
                int d1 = sgn((u.e-u.s)^(p[i]-u.s));
                int d2 = sgn((u.e-u.s)^(p[(i+1)%n]-u.s));
                if(d1 >= 0)po.p[top++] = p[i];
                if(d1*d2 < 0)po.p[top++] = u.crosspoint(Line(p[i],p[(i+1)%n]));
            }
        }
        //`得到周长`
        //`测试 LightOJ1239`
        double getcircumference(){
            double sum = 0;
            for(int i = 0;i < n;i++){
                sum += p[i].distance(p[(i+1)%n]);
            }
            return sum;
        }
        //`得到面积`
        double getarea(){
            double sum = 0;
            for(int i = 0;i < n;i++){
                sum += (p[i]^p[(i+1)%n]);
            }
            return fabs(sum)/2;
        }
        //`得到方向`
        //` 1 表示逆时针,0表示顺时针`
        bool getdir(){
            double sum = 0;
            for(int i = 0;i < n;i++)
                sum += (p[i]^p[(i+1)%n]);
            if(sgn(sum) > 0)return 1;
            return 0;
        }
        //`得到重心`
        Point getbarycentre(){
            Point ret(0,0);
            double area = 0;
            for(int i = 1;i < n-1;i++){
                double tmp = (p[i]-p[0])^(p[i+1]-p[0]);
                if(sgn(tmp) == 0)continue;
                area += tmp;
                ret.x += (p[0].x+p[i].x+p[i+1].x)/3*tmp;
                ret.y += (p[0].y+p[i].y+p[i+1].y)/3*tmp;
            }
            if(sgn(area)) ret = ret/area;
            return ret;
        }
        //`多边形和圆交的面积`
        //`测试:POJ3675 HDU3982 HDU2892`
        double areacircle(circle c){
            double ans = 0;
            for(int i = 0;i < n;i++){
                int j = (i+1)%n;
                if(sgn( (p[j]-c.p)^(p[i]-c.p) ) >= 0)
                    ans += c.areatriangle(p[i],p[j]);
                else ans -= c.areatriangle(p[i],p[j]);
            }
            return fabs(ans);
        }
        //`多边形和圆关系`
        //` 2 圆完全在多边形内`
        //` 1 圆在多边形里面,碰到了多边形边界`
        //` 0 其它`
        int relationcircle(circle c){
            getline();
            int x = 2;
            if(relationpoint(c.p) != 1)return 0;//圆心不在内部
            for(int i = 0;i < n;i++){
                if(c.relationseg(l[i])==2)return 0;
                if(c.relationseg(l[i])==1)x = 1;
            }
            return x;
        }
    };
    //`AB X AC`
    double cross(Point A,Point B,Point C){
        return (B-A)^(C-A);
    }
    //`AB*AC`
    double dot(Point A,Point B,Point C){
        return (B-A)*(C-A);
    }
    //`最小矩形面积覆盖`
    //` A 必须是凸包(而且是逆时针顺序)`
    //` 测试 UVA 10173`
    double minRectangleCover(polygon A){
        //`要特判A.n < 3的情况`
        if(A.n < 3)return 0.0;
        A.p[A.n] = A.p[0];
        double ans = -1;
        int r = 1, p = 1, q;
        for(int i = 0;i < A.n;i++){
            //`卡出离边A.p[i] - A.p[i+1]最远的点`
            while( sgn( cross(A.p[i],A.p[i+1],A.p[r+1]) - cross(A.p[i],A.p[i+1],A.p[r]) ) >= 0 )
                r = (r+1)%A.n;
            //`卡出A.p[i] - A.p[i+1]方向上正向n最远的点`
            while(sgn( dot(A.p[i],A.p[i+1],A.p[p+1]) - dot(A.p[i],A.p[i+1],A.p[p]) ) >= 0 )
                p = (p+1)%A.n;
            if(i == 0)q = p;
            //`卡出A.p[i] - A.p[i+1]方向上负向最远的点`
            while(sgn(dot(A.p[i],A.p[i+1],A.p[q+1]) - dot(A.p[i],A.p[i+1],A.p[q])) <= 0)
                q = (q+1)%A.n;
            double d = (A.p[i] - A.p[i+1]).len2();
            double tmp = cross(A.p[i],A.p[i+1],A.p[r]) *
                (dot(A.p[i],A.p[i+1],A.p[p]) - dot(A.p[i],A.p[i+1],A.p[q]))/d;
            if(ans < 0 || ans > tmp)ans = tmp;
        }
        return ans;
    }
    
    //`直线切凸多边形`
    //`多边形是逆时针的,在q1q2的左侧`
    //`测试:HDU3982`
    vector<Point> convexCut(const vector<Point> &ps,Point q1,Point q2){
        vector<Point>qs;
        int n = ps.size();
        for(int i = 0;i < n;i++){
            Point p1 = ps[i], p2 = ps[(i+1)%n];
            int d1 = sgn((q2-q1)^(p1-q1)), d2 = sgn((q2-q1)^(p2-q1));
            if(d1 >= 0)
                qs.push_back(p1);
            if(d1 * d2 < 0)
                qs.push_back(Line(p1,p2).crosspoint(Line(q1,q2)));
        }
        return qs;
    }
    //`半平面交`
    //`测试 POJ3335 POJ1474 POJ1279`
    //***************************
    struct halfplane:public Line{
        double angle;
        halfplane(){}
        //`表示向量s->e逆时针(左侧)的半平面`
        halfplane(Point _s,Point _e){
            s = _s;
            e = _e;
        }
        halfplane(Line v){
            s = v.s;
            e = v.e;
        }
        void calcangle(){
            angle = atan2(e.y-s.y,e.x-s.x);
        }
        bool operator <(const halfplane &b)const{
            return angle < b.angle;
        }
    };
    struct halfplanes{
        int n;
        halfplane hp[maxp];
        Point p[maxp];
        int que[maxp];
        int st,ed;
        void push(halfplane tmp){
            hp[n++] = tmp;
        }
        //去重
        void unique(){
            int m = 1;
            for(int i = 1;i < n;i++){
                if(sgn(hp[i].angle-hp[i-1].angle) != 0)
                    hp[m++] = hp[i];
                else if(sgn( (hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s) ) > 0)
                    hp[m-1] = hp[i];
            }
            n = m;
        }
        bool halfplaneinsert(){
            for(int i = 0;i < n;i++)hp[i].calcangle();
            sort(hp,hp+n);
            unique();
            que[st=0] = 0;
            que[ed=1] = 1;
            p[1] = hp[0].crosspoint(hp[1]);
            for(int i = 2;i < n;i++){
                while(st<ed && sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0)ed--;
                while(st<ed && sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0)st++;
                que[++ed] = i;
                if(hp[i].parallel(hp[que[ed-1]]))return false;
                p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
            }
            while(st<ed && sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0)ed--;
            while(st<ed && sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0)st++;
            if(st+1>=ed)return false;
            return true;
        }
        //`得到最后半平面交得到的凸多边形`
        //`需要先调用halfplaneinsert() 且返回true`
        void getconvex(polygon &con){
            p[st] = hp[que[st]].crosspoint(hp[que[ed]]);
            con.n = ed-st+1;
            for(int j = st,i = 0;j <= ed;i++,j++)
                con.p[i] = p[j];
        }
    };
    //***************************
    
    const int maxn = 1010;
    struct circles{
        circle c[maxn];
        double ans[maxn];//`ans[i]表示被覆盖了i次的面积`
        double pre[maxn];
        int n;
        circles(){}
        void add(circle cc){
            c[n++] = cc;
        }
        //`x包含在y中`
        bool inner(circle x,circle y){
            if(x.relationcircle(y) != 1)return 0;
            return sgn(x.r-y.r)<=0?1:0;
        }
        //圆的面积并去掉内含的圆
        void init_or(){
            bool mark[maxn] = {0};
            int i,j,k=0;
            for(i = 0;i < n;i++){
                for(j = 0;j < n;j++)
                    if(i != j && !mark[j]){
                        if( (c[i]==c[j])||inner(c[i],c[j]) )break;
                    }
                if(j < n)mark[i] = 1;
            }
            for(i = 0;i < n;i++)
                if(!mark[i])
                    c[k++] = c[i];
            n = k;
        }
        //`圆的面积交去掉内含的圆`
        void init_add(){
            int i,j,k;
            bool mark[maxn] = {0};
            for(i = 0;i < n;i++){
                for(j = 0;j < n;j++)
                    if(i != j && !mark[j]){
                        if( (c[i]==c[j])||inner(c[j],c[i]) )break;
                    }
                if(j < n)mark[i] = 1;
            }
            for(i = 0;i < n;i++)
                if(!mark[i])
                    c[k++] = c[i];
            n = k;
        }
        //`半径为r的圆,弧度为th对应的弓形的面积`
        double areaarc(double th,double r){
            return 0.5*r*r*(th-sin(th));
        }
        //`测试SPOJVCIRCLES SPOJCIRUT`
        //`SPOJVCIRCLES求n个圆并的面积,需要加上init\_or()去掉重复圆(否则WA)`
        //`SPOJCIRUT 是求被覆盖k次的面积,不能加init\_or()`
        //`对于求覆盖多少次面积的问题,不能解决相同圆,而且不能init\_or()`
        //`求多圆面积并,需要init\_or,其中一个目的就是去掉相同圆`
        void getarea(){
            memset(ans,0,sizeof(ans));
            vector<pair<double,int> >v;
            for(int i = 0;i < n;i++){
                v.clear();
                v.push_back(make_pair(-pi,1));
                v.push_back(make_pair(pi,-1));
                for(int j = 0;j < n;j++)
                    if(i != j){
                        Point q = (c[j].p - c[i].p);
                        double ab = q.len(),ac = c[i].r, bc = c[j].r;
                        if(sgn(ab+ac-bc)<=0){
                            v.push_back(make_pair(-pi,1));
                            v.push_back(make_pair(pi,-1));
                            continue;
                        }
                        if(sgn(ab+bc-ac)<=0)continue;
                        if(sgn(ab-ac-bc)>0)continue;
                        double th = atan2(q.y,q.x), fai = acos((ac*ac+ab*ab-bc*bc)/(2.0*ac*ab));
                        double a0 = th-fai;
                        if(sgn(a0+pi)<0)a0+=2*pi;
                        double a1 = th+fai;
                        if(sgn(a1-pi)>0)a1-=2*pi;
                        if(sgn(a0-a1)>0){
                            v.push_back(make_pair(a0,1));
                            v.push_back(make_pair(pi,-1));
                            v.push_back(make_pair(-pi,1));
                            v.push_back(make_pair(a1,-1));
                        }
                        else{
                            v.push_back(make_pair(a0,1));
                            v.push_back(make_pair(a1,-1));
                        }
                    }
                sort(v.begin(),v.end());
                int cur = 0;
                for(int j = 0;j < v.size();j++){
                    if(cur && sgn(v[j].first-pre[cur])){
                        ans[cur] += areaarc(v[j].first-pre[cur],c[i].r);
                        ans[cur] += 0.5*(Point(c[i].p.x+c[i].r*cos(pre[cur]),c[i].p.y+c[i].r*sin(pre[cur]))^Point(c[i].p.x+c[i].r*cos(v[j].first),c[i].p.y+c[i].r*sin(v[j].first)));
                    }
                    cur += v[j].second;
                    pre[cur] = v[j].first;
                }
            }
            for(int i = 1;i < n;i++)
                ans[i] -= ans[i+1];
        }
    };

    三维几何部分

    代码:

    const double eps = 1e-8;
    int sgn(double x){
        if(fabs(x) < eps)return 0;
        if(x < 0)return -1;
        else return 1;
    }
    struct Point3{
        double x,y,z;
        Point3(double _x = 0,double _y = 0,double _z = 0){
            x = _x;
            y = _y;
            z = _z;
        }
        void input(){
            scanf("%lf%lf%lf",&x,&y,&z);
        }
        void output(){
            scanf("%.2lf %.2lf %.2lf\n",x,y,z);
        }
        bool operator ==(const Point3 &b)const{
            return sgn(x-b.x) == 0 && sgn(y-b.y) == 0 && sgn(z-b.z) == 0;
        }
        bool operator <(const Point3 &b)const{
            return sgn(x-b.x)==0?(sgn(y-b.y)==0?sgn(z-b.z)<0:y<b.y):x<b.x;
        }
        double len(){
            return sqrt(x*x+y*y+z*z);
        }
        double len2(){
            return x*x+y*y+z*z;
        }
        double distance(const Point3 &b)const{
            return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
        }
        Point3 operator -(const Point3 &b)const{
            return Point3(x-b.x,y-b.y,z-b.z);
        }
        Point3 operator +(const Point3 &b)const{
            return Point3(x+b.x,y+b.y,z+b.z);
        }
        Point3 operator *(const double &k)const{
            return Point3(x*k,y*k,z*k);
        }
        Point3 operator /(const double &k)const{
            return Point3(x/k,y/k,z/k);
        }
        //点乘
        double operator *(const Point3 &b)const{
            return x*b.x+y*b.y+z*b.z;
        }
        //叉乘
        Point3 operator ^(const Point3 &b)const{
            return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
        }
        double rad(Point3 a,Point3 b){
            Point3 p = (*this);
            return acos( ( (a-p)*(b-p) )/ (a.distance(p)*b.distance(p)) );
        }
        //变换长度
        Point3 trunc(double r){
            double l = len();
            if(!sgn(l))return *this;
            r /= l;
            return Point3(x*r,y*r,z*r);
        }
    };
    struct Line3
    {
        Point3 s,e;
        Line3(){}
        Line3(Point3 _s,Point3 _e)
        {
            s = _s;
            e = _e;
        }
        bool operator ==(const Line3 v)
        {
            return (s==v.s)&&(e==v.e);
        }
        void input()
        {
            s.input();
            e.input();
        }
        double length()
        {
            return s.distance(e);
        }
        //点到直线距离
        double dispointtoline(Point3 p)
        {
            return ((e-s)^(p-s)).len()/s.distance(e);
        }
        //点到线段距离
        double dispointtoseg(Point3 p)
        {
            if(sgn((p-s)*(e-s)) < 0 || sgn((p-e)*(s-e)) < 0)
                return min(p.distance(s),e.distance(p));
            return dispointtoline(p);
        }
        //`返回点p在直线上的投影`
        Point3 lineprog(Point3 p)
        {
            return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
        }
        //`p绕此向量逆时针arg角度`
        Point3 rotate(Point3 p,double ang)
        {
            if(sgn(((s-p)^(e-p)).len()) == 0)return p;
            Point3 f1 = (e-s)^(p-s);
            Point3 f2 = (e-s)^(f1);
            double len = ((s-p)^(e-p)).len()/s.distance(e);
            f1 = f1.trunc(len); f2 = f2.trunc(len);
            Point3 h = p+f2;
            Point3 pp = h+f1;
            return h + ((p-h)*cos(ang)) + ((pp-h)*sin(ang));
        }
        //`点在直线上`
        bool pointonseg(Point3 p)
        {
            return sgn( ((s-p)^(e-p)).len() ) == 0 && sgn((s-p)*(e-p)) == 0;
        }
    };
    struct Plane
    {
        Point3 a,b,c,o;//`平面上的三个点,以及法向量`
        Plane(){}
        Plane(Point3 _a,Point3 _b,Point3 _c)
        {
            a = _a;
            b = _b;
            c = _c;
            o = pvec();
        }
        Point3 pvec()
        {
            return (b-a)^(c-a);
        }
        //`ax+by+cz+d = 0`
        Plane(double _a,double _b,double _c,double _d)
        {
            o = Point3(_a,_b,_c);
            if(sgn(_a) != 0)
                a = Point3((-_d-_c-_b)/_a,1,1);
            else if(sgn(_b) != 0)
                a = Point3(1,(-_d-_c-_a)/_b,1);
            else if(sgn(_c) != 0)
                a = Point3(1,1,(-_d-_a-_b)/_c);
        }
        //`点在平面上的判断`
        bool pointonplane(Point3 p)
        {
            return sgn((p-a)*o) == 0;
        }
        //`两平面夹角`
        double angleplane(Plane f)
        {
            return acos(o*f.o)/(o.len()*f.o.len());
        }
        //`平面和直线的交点,返回值是交点个数`
        int crossline(Line3 u,Point3 &p)
        {
            double x = o*(u.e-a);
            double y = o*(u.s-a);
            double d = x-y;
            if(sgn(d) == 0)return 0;
            p = ((u.s*x)-(u.e*y))/d;
            return 1;
        }
        //`点到平面最近点(也就是投影)`
        Point3 pointtoplane(Point3 p)
        {
            Line3 u = Line3(p,p+o);
            crossline(u,p);
            return p;
        }
        //`平面和平面的交线`
        int crossplane(Plane f,Line3 &u)
        {
            Point3 oo = o^f.o;
            Point3 v = o^oo;
            double d = fabs(f.o*v);
            if(sgn(d) == 0)return 0;
            Point3 q = a + (v*(f.o*(f.a-a))/d);
            u = Line3(q,q+oo);
            return 1;
        }
    };

    平面最近点对

    代码:

    const int MAXN = 100010;
    const double eps = 1e-8;
    const double INF = 1e20;
    struct Point{
        double x,y;
        void input(){
            scanf("%lf%lf",&x,&y);
        }
    };
    double dist(Point a,Point b){
        return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
    }
    Point p[MAXN];
    Point tmpt[MAXN];
    bool cmpx(Point a,Point b){
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
    bool cmpy(Point a,Point b){
        return a.y < b.y || (a.y == b.y && a.x < b.x);
    }
    double Closest_Pair(int left,int right){
        double d = INF;
        if(left == right)return d;
        if(left+1 == right)return dist(p[left],p[right]);
        int mid = (left+right)/2;
        double d1 = Closest_Pair(left,mid);
        double d2 = Closest_Pair(mid+1,right);
        d = min(d1,d2);
        int cnt = 0;
        for(int i = left;i <= right;i++){
            if(fabs(p[mid].x - p[i].x) <= d)
                tmpt[cnt++] = p[i];
        }
        sort(tmpt,tmpt+cnt,cmpy);
        for(int i = 0;i < cnt;i++){
            for(int j = i+1;j < cnt && tmpt[j].y - tmpt[i].y < d;j++)
                d = min(d,dist(tmpt[i],tmpt[j]));
        }
        return d;
    }
    int main(){
        int n;
        while(scanf("%d",&n) == 1 && n){
            for(int i = 0;i < n;i++)p[i].input();
            sort(p,p+n,cmpx);
            printf("%.2lf\n",Closest_Pair(0,n-1));
        }
        return 0;
    }

    三维凸包

    代码:

    const double eps = 1e-8;
    const int MAXN = 550;
    int sgn(double x){
        if(fabs(x) < eps)return 0;
        if(x < 0)return -1;
        else return 1;
    }
    struct Point3{
        double x,y,z;
        Point3(double _x = 0, double _y = 0, double _z = 0){
            x = _x;
            y = _y;
            z = _z;
        }
        void input(){
            scanf("%lf%lf%lf",&x,&y,&z);
        }
        bool operator ==(const Point3 &b)const{
            return sgn(x-b.x) == 0 && sgn(y-b.y) == 0 && sgn(z-b.z) == 0;
        }
        double len(){
            return sqrt(x*x+y*y+z*z);
        }
        double len2(){
            return x*x+y*y+z*z;
        }
        double distance(const Point3 &b)const{
            return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
        }
        Point3 operator -(const Point3 &b)const{
            return Point3(x-b.x,y-b.y,z-b.z);
        }
        Point3 operator +(const Point3 &b)const{
            return Point3(x+b.x,y+b.y,z+b.z);
        }
        Point3 operator *(const double &k)const{
            return Point3(x*k,y*k,z*k);
        }
        Point3 operator /(const double &k)const{
            return Point3(x/k,y/k,z/k);
        }
        //点乘
        double operator *(const Point3 &b)const{
            return x*b.x + y*b.y + z*b.z;
        }
        //叉乘
        Point3 operator ^(const Point3 &b)const{
            return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
        }
    };
    struct CH3D{
        struct face{
            //表示凸包一个面上的三个点的编号
            int a,b,c;
            //表示该面是否属于最终的凸包上的面
            bool ok;
        };
        //初始顶点数
        int n;
        Point3 P[MAXN];
        //凸包表面的三角形数
        int num;
        //凸包表面的三角形
        face F[8*MAXN];
        int g[MAXN][MAXN];
        //叉乘
        Point3 cross(const Point3 &a,const Point3 &b,const Point3 &c){
            return (b-a)^(c-a);
        }
        //`三角形面积*2`
        double area(Point3 a,Point3 b,Point3 c){
            return ((b-a)^(c-a)).len();
        }
        //`四面体有向面积*6`
        double volume(Point3 a,Point3 b,Point3 c,Point3 d){
            return ((b-a)^(c-a))*(d-a);
        }
        //`正:点在面同向`
        double dblcmp(Point3 &p,face &f){
            Point3 p1 = P[f.b] - P[f.a];
            Point3 p2 = P[f.c] - P[f.a];
            Point3 p3 = p - P[f.a];
            return (p1^p2)*p3;
        }
        void deal(int p,int a,int b){
            int f = g[a][b];
            face add;
            if(F[f].ok){
                if(dblcmp(P[p],F[f]) > eps)
                    dfs(p,f);
                else {
                    add.a = b;
                    add.b = a;
                    add.c = p;
                    add.ok = true;
                    g[p][b] = g[a][p] = g[b][a] = num;
                    F[num++] = add;
                }
            }
        }
        //递归搜索所有应该从凸包内删除的面
        void dfs(int p,int now){
            F[now].ok = false;
            deal(p,F[now].b,F[now].a);
            deal(p,F[now].c,F[now].b);
            deal(p,F[now].a,F[now].c);
        }
        bool same(int s,int t){
            Point3 &a = P[F[s].a];
            Point3 &b = P[F[s].b];
            Point3 &c = P[F[s].c];
            return fabs(volume(a,b,c,P[F[t].a])) < eps &&
                fabs(volume(a,b,c,P[F[t].b])) < eps &&
                fabs(volume(a,b,c,P[F[t].c])) < eps;
        }
        //构建三维凸包
        void create(){
            num = 0;
            face add;
    
            //***********************************
            //此段是为了保证前四个点不共面
            bool flag = true;
            for(int i = 1;i < n;i++){
                if(!(P[0] == P[i])){
                    swap(P[1],P[i]);
                    flag = false;
                    break;
                }
            }
            if(flag)return;
            flag = true;
            for(int i = 2;i < n;i++){
                if( ((P[1]-P[0])^(P[i]-P[0])).len() > eps ){
                    swap(P[2],P[i]);
                    flag = false;
                    break;
                }
            }
            if(flag)return;
            flag = true;
            for(int i = 3;i < n;i++){
                if(fabs( ((P[1]-P[0])^(P[2]-P[0]))*(P[i]-P[0]) ) > eps){
                    swap(P[3],P[i]);
                    flag = false;
                    break;
                }
            }
            if(flag)return;
            //**********************************
    
            for(int i = 0;i < 4;i++){
                add.a = (i+1)%4;
                add.b = (i+2)%4;
                add.c = (i+3)%4;
                add.ok = true;
                if(dblcmp(P[i],add) > 0)swap(add.b,add.c);
                g[add.a][add.b] = g[add.b][add.c] = g[add.c][add.a] = num;
                F[num++] = add;
            }
            for(int i = 4;i < n;i++)
                for(int j = 0;j < num;j++)
                    if(F[j].ok && dblcmp(P[i],F[j]) > eps){
                        dfs(i,j);
                        break;
                    }
            int tmp = num;
            num = 0;
            for(int i = 0;i < tmp;i++)
                if(F[i].ok)
                    F[num++] = F[i];
        }
        //表面积
        //`测试:HDU3528`
        double area(){
            double res = 0;
            if(n == 3){
                Point3 p = cross(P[0],P[1],P[2]);
                return p.len()/2;
            }
            for(int i = 0;i < num;i++)
                res += area(P[F[i].a],P[F[i].b],P[F[i].c]);
            return res/2.0;
        }
        double volume(){
            double res = 0;
            Point3 tmp = Point3(0,0,0);
            for(int i = 0;i < num;i++)
                res += volume(tmp,P[F[i].a],P[F[i].b],P[F[i].c]);
            return fabs(res/6);
        }
        //表面三角形个数
        int triangle(){
            return num;
        }
        //表面多边形个数
        //`测试:HDU3662`
        int polygon(){
            int res = 0;
            for(int i = 0;i < num;i++){
                bool flag = true;
                for(int j = 0;j < i;j++)
                    if(same(i,j)){
                        flag = 0;
                        break;
                    }
                res += flag;
            }
            return res;
        }
        //重心
        //`测试:HDU4273`
        Point3 barycenter(){
            Point3 ans = Point3(0,0,0);
            Point3 o = Point3(0,0,0);
            double all = 0;
            for(int i = 0;i < num;i++){
                double vol = volume(o,P[F[i].a],P[F[i].b],P[F[i].c]);
                ans = ans + (((o+P[F[i].a]+P[F[i].b]+P[F[i].c])/4.0)*vol);
                all += vol;
            }
            ans = ans/all;
            return ans;
        }
        //点到面的距离
        //`测试:HDU4273`
        double ptoface(Point3 p,int i){
            double tmp1 = fabs(volume(P[F[i].a],P[F[i].b],P[F[i].c],p));
            double tmp2 = ((P[F[i].b]-P[F[i].a])^(P[F[i].c]-P[F[i].a])).len();
            return tmp1/tmp2;
        }
    };
    CH3D hull;
    int main()
    {
        while(scanf("%d",&hull.n) == 1){
            for(int i = 0;i < hull.n;i++)hull.P[i].input();
            hull.create();
            Point3 p = hull.barycenter();
            double ans = 1e20;
            for(int i = 0;i < hull.num;i++)
                ans = min(ans,hull.ptoface(p,i));
            printf("%.3lf\n",ans);
        }
        return 0;
    }

    转载于:https://www.cnblogs.com/Staceyacm/p/10797445.html

    展开全文
  • POJ 2318 TOYS 题意:m个玩具落在n+1个区间,给你玩具的坐标,问每个区间有多少玩具。 思路:叉积的简单应用,用叉积判断在直线的哪一侧,因为是顺序给出坐标,所以从左往右判断即可。 ...cma...
  • (为了套板子,写的很繁琐) 2.poj2007 Scrambled Polygon 题目: http://poj.org/problem?id=2007 题意:求一个凸多边形的凸包。要求起始点为输入的第一个点。 分析:rt。 1 #include 2 #include...
  • 大菜鸡的计算几何之旅-[kuangbin带你飞]专题十三 基础计算几何 A POJ 2318 TOYS Description Calculate the number of toys that land in each bin of a partitioned toy box. Mom and dad have a problem - their ...
  • 1.poj3335Rotating Scoreboard ... 题意:就是有个球场,球场的形状是个凸多边形,然后观众是坐在多边形的边上的,问你是否在球场上有个地方可以放一个记分牌,然后所有的观众都可以看得到的。 分析:多边形是否存在...
  • acm计算几何模板

    2019-05-09 15:43:08
    不要过分相信的我抄的,我在用的时候也经常会遇到错,所以如果不对,还请自己改,或者自己找一份原kuangbin大佬的计算几何板子。 # include using namespace std ; # define me(x,y) memset(x,y,sizeof x)...
  • 附上做这套专题的模板(该专题只有点线面的关系所以这些模板就够了) const db EPS=1e-9; inline int sign(db a){return a&lt;-EPS?-1:a&gt;EPS;} inline int cmp(db a,db b){return sign(a-b);...
  • 这两天要花时间研究一下kuangbin计算几何模板,至少我要知道该怎么用才可以。 ac code #include <bits/stdc++.h> #define pb push_back #define ld long double using namespace std; cons
  • ACM Template of kuangbin 3 数据结构 56 3.1 划分树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2 RMQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....
  • 计算几何

    2020-10-28 14:43:06
    10/28学计算几何 三角形三个顶点画圆,求面积最大=[a12+ (a2-a1)2]*PI 裁缝大师,给圆心(x,y)&半径(rad),在这个圆找n个点使其构成正n边形 思路:将圆心角等分成n份,用cos(a)*r求出x坐标,sin(a)*rad求出y...
  • 下面给出两种不同风格的代码,一种是网上找的,便于理解,一种是从kuangbin模板上摘下来的,适用性更广,可以当作板子用。其中对于给出点的顺时针和逆时针顺序不同,邝斌模板只需要加个 reverse 函数将点的顺序颠倒...
  • 计算几何相关问题

    2020-08-08 22:53:25
    计算几何是直接可以拿kuangbin板子进行写的,但是还是需要有自己的一些储备。 方法:从平面几何->解析几何 首先,我们需要判断浮点数符号。 const double eps = 1e-8; //... int sgn(double x) { if (fabs(x) ...
  • 计算几何模板

    2019-08-28 03:00:19
    kuangbin板子 int sgn(double x) { //符号函数 if (fabs(x) < eps) return 0; if (x < 0) return -1; else return 1; } struct Point { //点 double x, y; Point() { } Point(double _x, double _...
  • 计算几何的题还是写的少,调了一个小时的蜜汁bug最后发现被卡精度了,得用long double,这题思路上并不难,先判断一下直线AV是否与圆的交点个数,如果少于2个交点,判断B是否在射线AV上,如果有两个交点,求出距离A...
  • 找到适合的模板 前期用kuangbin板子磕磕绊绊敲题 现在用经诗姐姐的板子(感谢经诗姐姐!)后期研究出适合自己手感的板子(自己造板子) 千万千万不要敲错板子!! 在大量计算过程中注意精度控制 如果wa了要考虑...
  • ACM竞赛板子

    2021-08-19 22:02:01
    自己的板子积累,不断更新中 数学 欧拉筛(线性筛) 时间复杂度O(n) void prime(int n) { for(int i=2; i<=n; i++) { if(!st[i]) p[ans++]=i; for(int j=0; p[j]<=n/i; j++) { st[p[j]*i]=1; if(i%...
  • 代码: 注:直接套了kuangbin计算几何板子,很长 #include #include #include #include #include using namespace std; const double eps = 1e-8; const double inf = 1e20; const double pi = acos(-1.0); const...
  • 判断线段和直线相交可以用kuangbin板子,我解斜截式直线方程,分斜率是否存在讨论。 /* Author : Rshs */ #include<bits/stdc++.h> using namespace std; #define FI first #define SE second #define LL ...
  • 文章目录专题十三 基础计算几何POJ 2318 TOYSPOJ 2398 Toy StoragePOJ 3304 SegmentsPOJ 1269 Intersecting LinesPOJ 1556 The DoorsPOJ 2653 Pick-up sticksPOJ 1066 Treasure HuntPOJ 1410 IntersectionPOJ 1696 ...
  • here 要在n个点中选中4个点求一个矩形的最大面积。 如果枚举点的话复杂度实在太高了...kuangbin板子还是看着不太习惯,这几天适应一下吧!下边是我自己写的不是他的板子。 ac code //god with me #include <bits/s
  • 解释与代码 kuangbin板子 真就无脑暴力呗,正好卡在时限内,再多一点就超时了 #include #include #include #include #include #include #include #include #include #include #include #include #include #include ...
  • //要看一下是否在线段上,因为有可能求出的点在延长线上 if(l[i].pointonseg1(temp)){ //这里要吐槽一下kuangbin大神的板子,好像只能判断是否在直线上,并不能判断是否在线段上 //所以,我又写了个函数判断求得点...
  • kuangbin 大大的板子(侵删) 这道题首先可以确认的是最远点对一定在凸包上。 求出凸包以后,作两点的平行线,当一点到平行线的方向发生改变时达到可能的最大值(旋转卡壳)。然后旋转到每个点都考虑完毕就可以...
  • 直接用kuangbin板子,能判不规范,规范和不交 另外线段在矩形内也可以,判断方式是比较线段的端点和矩形四个角 #include <cstdio> #include <cmath> #include <algorithm> #include <...
  • 前一段时间做了kuangbin带你飞基础数论专题部分,可看了不少的相关的资料,在这里也来做一个总结。 由于数论方面的知识太多...杜教筛等等还没学)的汇总,关于数论的板子等学完计算几何和组合数学之后找个时间再汇...

空空如也

空空如也

1 2 3
收藏数 59
精华内容 23
关键字:

kuangbin计算几何板子