[Nowcoder Multi Univerisity Training 2G]Polygons

Link

辣鸡题目

Code

const int XN=1e3+11,XV=1e6+11;
const double eps=1e-10,inf=1e10;

int sgn(double const &x) {
    return (x>-eps)-(x<eps);
}

double p2(double const &x) { 
    return x*x;
}

struct Point {
    double x,y;

    double Length() const {
        return sqrt(x*x+y*y);
    }

    Point Normal() const {
        return {-y,x};
    }

    Point Unit() const {
        double len=Length();
        return Point{x/len,y/len};
    }

    friend Point operator +(const Point &a,const Point &b) {
        return {a.x+b.x,a.y+b.y};
    }

    friend Point operator -(const Point &a,const Point &b) {
        return {a.x-b.x,a.y-b.y};
    }

    friend Point operator *(const Point &a,const double &k) {
        return Point{a.x*k,a.y*k};
    }

    friend Point operator /(const Point &a,const double &k) {
        return Point{a.x/k,a.y/k};
    }

    friend double Inner(const Point &a,const Point &b) {
        return a.x*b.x+a.y*b.y;
    }

    friend double Outer(const Point &a,const Point &b) {
        return a.x*b.y-a.y*b.x;
    }
};

struct Line {
    Point p,v;
};

double Dist(const Point &a,const Point &b) {
    return (a-b).Length();
}

double Dist(const Point &a,Line const &l) {
    return fabs(Outer(a-l.p,l.v))/l.v.Length();
}

Point Cross(Line const &l1,Line const &l2) {
    double t=Outer(l2.v,l1.p-l2.p)/Outer(l1.v,l2.v);
    return l1.p+l1.v*t;
}

double cos(Point const &a,Point const &b) {
    return Inner(a,b)/a.Length()/b.Length();
}
int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;
    std::cin>>n;
    std::vector<Line> l;
    for(int i=1;i<=n;++i) {
        Point p1,p2;
        std::cin>>p1.x>>p1.y>>p2.x>>p2.y;
        l.push_back({p1,p2-p1});
    }
    std::vector<Point> cross;
    static std::vector<int> cut[XN];
    for(size_t i=0;i<l.size();++i)
        for(size_t j=i+1;j<l.size();++j)
            if(Outer(l[i].v,l[j].v)!=0) {
                cut[i].push_back(cross.size());
                cut[j].push_back(cross.size());
                cross.push_back(Cross(l[i],l[j]));
            }
    static std::vector<int> G[XV];
    for(size_t i=0;i<l.size();++i) {
        std::sort(cut[i].begin(),cut[i].end(),[&](int x,int y)->bool {
            return Inner(cross[x]-l[i].p,l[i].v)<Inner(cross[y]-l[i].p,l[i].v);
        });
        for(size_t j=0;j+1<cut[i].size();++j) {
            //std::cerr<<i<<' '<<j<<'\n';
            G[cut[i][j]].push_back(cut[i][j+1]);
            G[cut[i][j+1]].push_back(cut[i][j]);
        }
    }
    //一个交点最多4条线啊
    std::vector<double> area;
    for(size_t i=0;i<cross.size();++i)
        while(G[i].size()) {
            Point v=cross[G[i].front()]-cross[i];
            double size=0;
            int pos=G[i].front();
            for(int nxt;G[pos].size();pos=nxt) {
                auto iter=std::find(G[pos].begin(),G[pos].end(),i);
                if(iter!=G[pos].end() && size!=0) {
                    area.push_back(size/=2);
                    G[pos].erase(iter);
                    break;
                } else {
                    iter=std::min_element(G[pos].begin(),G[pos].end(),[&](int x,int y)->bool {
                        double ox=Outer(v,cross[x]-cross[pos]),oy=Outer(v,cross[y]-cross[pos]),
                            cx=cos(v,cross[x]-cross[pos]),cy=cos(v,cross[y]-cross[pos]);
                        if(sgn(ox)<=0 || sgn(oy)<=0)
                            return sgn(ox)>0;
                        else
                            return cx<cy;
                    });
                    if(Outer(v,cross[nxt=*iter]-cross[pos])>0) {
                        size+=Outer(cross[pos]-cross[i],cross[nxt]-cross[i]);
                        G[pos].erase(iter);
                        v=cross[nxt]-cross[pos];
                    } else
                        break;
                }
            }
            G[i].erase(G[i].begin());
        }
    std::sort(area.begin(),area.end(),std::greater<double>());
    std::cout.precision(10);
    std::cout<<area.size()<<' '<<area.front()<<' '<<area.back()<<'\n';
    int m;std::cin>>m;
    while(m--) {
        int k;std::cin>>k;--k;
        if(k>=(int)area.size())
            std::cout<<"Invalid question\n";
        else
            std::cout<<area[k]<<'\n';
    }
    return 0;
}

[ICPC 2017 ECNA B]Craters

Link

Solution

求出所有可能在凸包上的切线,然后半平面交。。。
二维量的eps比较微妙

Code

const int XN=1e5+11;
const double eps=1e-4,inf=1e100,pi=acos(-1);

int sgn(double const &x) {
    return (x>-eps)-(x<eps);
}

struct Point {
    double x,y;

    double Length() const {
        return sqrt(x*x+y*y);
    }

    double Length2() const {
        return x*x+y*y;
    }

    Point Unit() const {
        double len=sqrt(x*x+y*y);
        return {x/len,y/len};
    }

    Point TurnRight() const {
        return {y,-x};
    }

    friend Point operator +(Point const &a,Point const &b) {
        return {a.x+b.x,a.y+b.y};
    }

    friend Point operator -(Point const &a,Point const &b) {
        return {a.x-b.x,a.y-b.y};
    }

    friend Point operator *(Point const &p,double const &k) {
        return {p.x*k,p.y*k};
    }

    friend double Inner(Point const &a,Point const &b) {
        return a.x*b.x+a.y*b.y;
    }

    friend double Outer(Point const &a,Point const &b) {
        return a.x*b.y-a.y*b.x;
    }

    friend double Dist(Point const &a,Point const &b) {
        return sqrt(Inner(a-b,a-b));
    }

    friend bool operator <(Point const &a,Point const &b) {
        return a.x<b.x || (a.x==b.x && a.y<b.y);
    }

    friend bool operator ==(Point const &a,Point const &b) {
        return a.x==b.x && a.y==b.y;
    }
}p[XN];

struct Circle {
    Point o;
    double r;

    bool Include(Circle const &a) {
        return sgn(a.r+Dist(o,a.o)-r)<=0;
    }
}o[XN];

struct Line {
    Point p,v;

    friend bool operator <(Line const &a,Line const &b) {
        return a.p<b.p || (a.p==b.p && a.v<b.v);
    }
};

double Dist(Point const &a,Line const &l) {
    return fabs(Outer(a-l.p,l.v))/l.v.Length();
}

bool OnLeft(Point const &p,Line const &ln) {
    return sgn(Outer(ln.v,p-ln.p))>0;
}

bool Paral(Line const &ln1,Line const &ln2) {
    return sgn(Outer(ln1.v,ln2.v))==0;
}

Point Cross(Line const &ln1,Line const &ln2) {
    if(Paral(ln1,ln2)) {
        return ln1.p+ln1.v*inf;
    } else {
        double t=Outer(ln2.v,ln1.p-ln2.p)/Outer(ln1.v,ln2.v);
        return ln1.p+ln1.v*t;
    }
}

Point CutPoint(Point const &p,Circle const &a) {
    if(sgn(Dist(p,a.o)-a.r)==0)
        return p;
    else {
        double x=Dist(p,a.o),cosa=a.r/x,sina=sqrt(1-cosa*cosa);
        Point v=(p-a.o).Unit(),
              t={v.x*cosa-v.y*sina,v.y*cosa+v.x*sina};
        return a.o+t*a.r;
    }
}

Point Mirror(Point const &p,Line const &l) {
    Point foot=l.p+l.v.Unit()*(Inner(p-l.p,l.v)/l.v.Length());
    return foot+(foot-p);
}

Line Cut(Circle const &a,Circle const &b) {
    /*a--b   b|
      ----   a|
      */
    if(sgn(a.r-b.r)==0) {
        return {a.o+(b.o-a.o).Unit().TurnRight()*a.r,b.o-a.o};
    } else {
        double d=Dist(a.o,b.o),
               x=a.r*d/(b.r-a.r);
        Point c=a.o+(a.o-b.o).Unit()*x,
              p=CutPoint(c,a);
        if(a.r>b.r) {
            p=Mirror(p,{a.o,b.o-a.o});
            return {p,c-p};
        } else
            return {c,p-c};
    }
}

std::vector<Line> Intersect(std::vector<Line> &ln) {
    std::sort(ln.begin(),ln.end(),[](Line const &a,Line const &b)->bool {
                auto Quad=[](Point const &a)->int {
                    return sgn(a.x)>0 && sgn(a.y)>=0?1:
                            (sgn(a.x)<=0 && sgn(a.y)>0?2:
                            (sgn(a.x)<0 && sgn(a.y)<=0?3:4));
                };
                int qa=Quad(a.v),qb=Quad(b.v);
                return qa==qb?sgn(Outer(b.v,a.v))<0:qa<qb;
            });
    static Point Qp[XN];static Line Qln[XN];
    int n=ln.size();
    int head,tail;Qln[head=tail=1]=ln[0];
    for(int i=1;i<n;++i) {
        while(tail-head>=1 && !OnLeft(Qp[tail-1],ln[i]))
            tail--;
        while(tail-head>=1 && !OnLeft(Qp[head],ln[i]))
            head++;
        Qln[++tail]=ln[i];
        if(Paral(Qln[tail-1],Qln[tail])){
            int d1=OnLeft(Qln[tail].p,Qln[tail-1]),d2=OnLeft(Qln[tail-1].p,Qln[tail]);
            if(!d1 || !d2) {
                tail--;
                if(d1)
                    Qln[tail]=ln[i];
            }
        }
        if(tail-head>=1)
            Qp[tail-1]=Cross(Qln[tail-1],Qln[tail]);
    }
    while(tail-head>=1 && !OnLeft(Qp[tail-1],Qln[head]))
        tail--;
    if(tail-head>=1)
        return std::vector<Line>(Qln+head,Qln+tail+1);
    else
        return {};
}

double ArcLen(double const &len,double const &r) {
    return r*asin(len/2/r)*2;
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    srand(0x1f1f1f1f);
    int n;std::cin>>n;
    for(int i=1;i<=n;++i) {
        std::cin>>o[i].o.x>>o[i].o.y>>o[i].r;
        o[i].r+=10;
    }
    static bool ban[XN];
    for(int i=1;i<=n;++i)
        if(!ban[i]) {
            for(int j=1;j<=n;++j)
                if(i!=j && o[i].Include(o[j]))
                    ban[j]=1;
        }
    int cc=0;
    for(int i=1;i<=n;++i)
        if(!ban[i])
            o[++cc]=o[i];
    n=cc;
    double Ans=0;
    if(n==1)
        Ans=2*pi*o[1].r;
    else {
        std::map<Line,std::pair<int,int>> id;
        std::vector<Line> v;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j) 
                if(i!=j) {
                    Line cut=Cut(o[i],o[j]);
                    /*
                    for(auto x : {o[i],o[j]})
                        std::cerr<<Dist(x.o,cut)<<' '<<x.r<<'\n';
                    */
                    bool tak=1;
                    for(int k=1;k<=n;++k)
                        tak&=OnLeft(o[k].o,cut) && sgn(Dist(o[k].o,cut)-o[k].r)>=0;
                    if(tak)
                        v.push_back(cut);
                }
        v=Intersect(v);
        int s=v.size();
        std::vector<std::array<Point,2>> cp(s);
        std::vector<int> ids(s);
        for(int i=0;i<s;++i) {
            double mx=-inf,mn=inf;
            for(int j=1;j<=n;++j) {
                Point pts[2];
                pts[1]=Mirror(pts[0]=CutPoint(v[i].p,o[j]),{v[i].p,o[j].o-v[i].p});
                for(int d=0;d<2;++d)
                    if(sgn(Outer(pts[d]-v[i].p,v[i].v))==0) {
                        double t=Inner(pts[d]-v[i].p,v[i].v)/v[i].v.Length2();
                        if(Enlarge(mx,t)) {
                            cp[(i+1)%s][0]=pts[d];
                            ids[(i+1)%s]=j;
                        }
                        if(Reduce(mn,t)) {
                            cp[i][1]=pts[d];
                        }
                        break;
                    }
            }
        }
        for(int i=0;i<s;++i)
            Ans+=Dist(cp[i][1],cp[(i+1)%s][0])+ArcLen(Dist(cp[i][0],cp[i][1]),o[ids[i]].r);
    }
    std::cout<<std::fixed<<std::setprecision(10)<<Ans<<'\n';
    return 0;
}

[ICPC 2018 Asia Yokohama Onsite F]Fair Chocolate Cutting

Link

Solution

最长的距离,貌似一定一端在顶点上。
最短的距离,固定一个端点在一条边上,那么这条平分线的长度貌似应该是单峰的。
然后就扫一遍,三分三分,就OK了。
然而正解……

Code

const int XN=5000+11;
const long double inf=1e100;

struct Point {
    long double x,y;

    friend Point operator +(Point const &a,Point const &b) {
        return {a.x+b.x,a.y+b.y};
    }

    friend Point operator -(Point const &a,Point const &b) {
        return {a.x-b.x,a.y-b.y};
    }

    friend Point operator *(Point const &p,long double const &k) {
        return {p.x*k,p.y*k};
    }

    friend long double Inner(Point const &a,Point const &b) {
        return a.x*b.x+a.y*b.y;
    }

    friend long double Outer(Point const &a,Point const &b) {
        return a.x*b.y-a.y*b.x;
    }

    friend long double Dist(Point const &a,Point const &b) {
        return sqrt(Inner(a-b,a-b));
    }
}p[XN];

long double Length(Point a,Point b,long double t,Point c,Point d,long double size) {
    //a+(b-a)*t 在cd上找 让bd部分为size的线
    Point v=a+(b-a)*t;
    long double req=(Outer(b-a,c-a)+Outer(c-a,d-a))/2-size-Outer(v-a,d-a)/2;
    //(v-d) x (t*(c-d))=2*size
    long double l=2*req/Outer(v-d,c-d);
    return Dist(v,d+(c-d)*l);
}

long double SolveMin(Point a,Point b,Point c,Point d,long double size) {
    long double l=0,r=1;
    while(r-l>1e-15) {
        long double m1=l+(r-l)/3,m2=r-(r-l)/3;
        if(Length(a,b,m1,c,d,size)>Length(a,b,m2,c,d,size))
            l=m1;
        else
            r=m2;
    }
    return Length(a,b,l,c,d,size);
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;std::cin>>n;
    for(int i=0;i<n;++i)
        std::cin>>p[i].x>>p[i].y;
    long double size=0;
    for(int i=2;i<n;++i)
        size+=Outer(p[i-1]-p[0],p[i]-p[0]);

    size/=2;

    long double AnsMax=-inf,AnsMin=inf,sum=0;
    for(int l=0,r=1;l<n;sum-=Outer(p[(l+1)%n]-p[l],p[r]-p[l])/2,++l) {
        for(long double d=0;sum+(d=Outer(p[r]-p[l],p[(r+1)%n]-p[l])/2)<size/2;sum+=d,(r+=1)%=n);
        Enlarge(AnsMax,Length(p[l],p[l],0,p[r],p[(r+1)%n],size/2-sum));
        Reduce(AnsMin,SolveMin(p[l==0?n-1:l-1],p[l],p[r],p[(r+1)%n],size/2-sum));
    }
    std::cout<<std::fixed<<std::setprecision(10)<<AnsMin<<'\n'<<AnsMax<<'\n';
    return 0;
}

[ICPC 2018 Beijing Onsite J]Rikka with Triangles

Link

Solution

以每个点为原点,将剩下的点排极角序,然后按顺序枚举剩下的点,记录它上方的,以这两点连线为一边的锐角和钝角直角分别的x,y坐标和。就可以用叉积公式算面积了。
这样做,锐角三角形会被3个锐角计入三次,其他三角形会锐角计入2次,那么当作为非锐角被计入时,就减去两倍的面积。
最后剩下的是所有锐角三角形面积和的三倍,/3输出即可。

Code

const int P=998244353;

int Pow(long long base,int v) {
    static long long res;
    for(res=1;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

const int XN=2e3+11,inv3=Pow(3,P-2);

struct Point {
    long long x,y;

    friend Point operator -(Point const &a,Point const &b) {
        return {a.x-b.x,a.y-b.y};
    }

    friend __int128 Inner(Point const &a,Point const &b) {
        return (__int128)a.x*b.x+(__int128)a.y*b.y;
    }

    friend __int128 Outer(Point const &a,Point const &b) {
        return (__int128)a.x*b.y-(__int128)a.y*b.x;
    }
}p[XN],g[XN*2];

void Work() {
    int n;std::cin>>n;
    for(int i=0;i<n;++i)
        std::cin>>p[i].x>>p[i].y;
    long long Ans=0;
    for(int c=0;c<n;++c) {
        for(int i=0;i<n;++i)
            g[i]=p[i]-p[c];
        std::swap(g[c],g[0]);
        std::sort(g+1,g+n,[](Point const &a,Point const &b)->bool {
                    auto Quad=[](Point const &a)->int {
                        return a.x>0 && a.y>=0?1:(a.x<=0 && a.y>0?2:(a.x<0 && a.y<=0?3:4));
                    };
                    int qa=Quad(a),qb=Quad(b);
                    return qa==qb?Outer(b,a)<0:qa<qb;
                });
        static long long xs[XN*2],ys[XN*2];
        for(int i=1;i<n;++i)
            g[n+i-1]=g[i];
        for(int i=1;i<2*n-1;++i) {
            xs[i]=(xs[i-1]+g[i].x)%P;
            ys[i]=(ys[i-1]+g[i].y)%P;
        }
        for(int i=1,le=1;i<n;++i) {
            auto FindLast=[&](int L,int R,std::function<bool(Point)> Judge)->int {//Last Satisfies Judge(g[i])
                    while(L!=R) {
                        int M=(L+R+1)/2;
                        if(Judge(g[M]))
                            L=M;
                        else
                            R=M-1;
                    }
                    return L;
                };
            Enlarge(le,i);
            while(Outer(g[i],g[le])==0)
                ++le;
            Point neg={-g[i].x,-g[i].y};
            if(Outer(g[le],neg)>0) {
                int oppo=FindLast(le,i+n-1,[&](Point const &p)-> bool { return Outer(p,neg)>0; });
                Point axis={-g[i].y,g[i].x};
                int mid=Outer(g[le],axis)>0?FindLast(le,oppo,[&](Point const &p)->bool { return Outer(p,axis)>0; }):le-1;
                (Ans+=g[i].x%P*(3*ys[mid]-2*ys[oppo]-ys[le-1])%P-g[i].y%P*(3*xs[mid]-2*xs[oppo]-xs[le-1])%P)%=P;
            }
        }
    }
    Ans<0 && (Ans+=P);
    (Ans*=inv3)%=P;
    std::cout<<Ans<<'\n';
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

[ICPC 2018 Shenyang Onsite L][Gym 101955L]Machining Disc Rotors

Link

Solution

最远点对一定出现在一对交点处,或者交点和它的未被覆盖的对称点处。考虑弦长变化的单调性即可证明。

Code

const int XN=2e2+11;
const double eps=1e-10,pi=acos(-1);

int sgn(double const &x) {
    return (x>-eps)-(x<eps);
}

struct Point {
    double x,y;

    double Length() const {
        return sqrt(x*x+y*y);
    }

    Point Normal() const {
        return Point{-y,x};
    }

    Point Unit() const {
        double len=Length();
        return Point{x/len,y/len};
    }

    friend Point operator +(const Point &a,const Point &b) {
        return Point{a.x+b.x,a.y+b.y};
    }

    friend Point operator -(const Point &a,const Point &b) {
        return Point{a.x-b.x,a.y-b.y};
    }

    friend Point operator *(const Point &a,const double &k) {
        return Point{a.x*k,a.y*k};
    }

    friend Point operator /(const Point &a,const double &k) {
        return Point{a.x/k,a.y/k};
    }

    friend double Inner(const Point &a,const Point &b) {
        return a.x*b.x+a.y*b.y;
    }

    friend double Outer(const Point &a,const Point &b) {
        return a.x*b.y-a.y*b.x;
    }
};

double Dist(const Point &a,const Point &b) {
    return (a-b).Length();
}

void Work() {
    int n,R;fin>>n>>R;
    Point o{0,0};
    auto Atan2=[](double const &y,double const &x) { double r=atan2(y,x); return r<0?r+pi*2:r; };
    bool flag=0;
    auto Calc=[&](Point p,int r)->std::vector<Point> {
        int d1=sgn(Dist(o,p)-R-r),d2=sgn(Dist(o,p)-fabs(R-r));
        if(d1==0)
            return {p/(R+r)*R};
        else if(d1<0 && d2==0) {
            return {p/(R-r)*R};
        } else if(d1<0 && d2>0) {
            double d=Dist(o,p),x=(R*R-r*r+d*d)/(2*d),h=sqrt(R*R-x*x);
            Point v=(p-o).Unit(),n=v.Normal();
            return {v*x-n*h,v*x+n*h};
        } else
            return {};
    };

    std::vector<Point> cross;
    std::vector<std::pair<double,double> > ranges;
    for(int i=1;i<=n;++i) {
        int x,y,r;
        fin>>x>>y>>r;
        std::vector<Point> nc=Calc(Point{(double)x,(double)y},r);
        for(Point &p : nc)
            cross.push_back(p);
        if(nc.size()==1) {
            double x=Atan2(nc[0].y,nc[0].x);
            ranges.push_back({x,x});
        } else if(nc.size()==2)
            ranges.push_back({Atan2(nc[0].y,nc[0].x),Atan2(nc[1].y,nc[1].x)});
    }
    std::sort(ranges.begin(),ranges.end());
    double Ans=0;
    for(size_t i=0;i<cross.size();++i) {
        for(size_t j=i+1;j<cross.size();++j)
            Enlarge(Ans,Dist(cross[i],cross[j]));
        double ang=Atan2(-cross[i].y,-cross[i].x);
        auto Cover=[&](std::pair<double,double> const &x,double const &y)->bool {
            if(x.first<=x.second)
                return x.first<=y && y<=x.second;
            else
                return x.first<=y || y<=x.second;
        };
        auto iter=std::upper_bound(ranges.begin(),ranges.end(),std::pair<double,double>(ang,ang));
        if(iter!=ranges.begin())
            flag|=!Cover(*--iter,ang) && !Cover(ranges.back(),ang);
        else
            flag|=!Cover(ranges.back(),ang);
        if(flag)
            break;
    }
    if(flag)
        Ans=R*2;
    fout<<Ans<<'\n';
}

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        Work();
    }
    return 0;
}