Kingdom Rush 5: Alliance 题解

Colin is a huge fan of the Kingdom Rush franchise tower defense games. Last year, KR released the latest generation of Kingdom Rush: Kingdom Rush 5: Alliance. As a formidable evil arises in the new generation, an unexpected alliance is taking shape! It will take the finest warriors of Linirea and the relentless Dark Army together to stop it. Therefore, the most attractive feature of the latest generation of games is that you can use two heroes simultaneously!

To measure the power of the double-hero feature, Colin would like to do some simple experiments: Assume that a hero's attack range is a circle on the 2D plane with its coordinates as the center. The path of enemies is a segment on the 2D plane. Colin would like to ask you how long is the total length of the enemy's path that is covered by at least one hero's attack range? 计算几何 抄板子就完事了

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
//#define int long long

const double pi=acos(-1.0);
const double eps=1e-8;

int sgn(double x)
{
    if(fabs(x)<eps)return 0;
    else return x<0?-1:1;
}

struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    
    Point operator + (Point B){return Point(x+B.x,y+B.y);}
    Point operator - (Point B){return Point(x-B.x,y-B.y);}
    Point operator * (double k){return Point(x*k,y*k);}
    Point operator / (double k){return Point(x/k,y/k);}
};
typedef Point Vector;
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
double Distance(Point A,Point B){return hypot(A.x-B.x,A.y-B.y);}

struct Line{
    Point p1,p2;
    Line(){}
    Line(Point p1,Point p2):p1(p1),p2(p2){}
    Line(Point p,double angle){
        p1=p;
        if(sgn(angle-pi/2)==0){p2=(p1+Point(1,tan(angle)));}
    }
    Line(double a,double b,double c)
    {
        if(sgn(a)==0)
        {
            p1=Point(0,-c/b);
            p2=Point(0,-c/b);
        }
        else if(sgn(b)==0)
        {
            p1=Point(-c/a,0);
            p2=Point(-c/a,1);
        }
        else
        {
            p1=Point(0,-c/b);
            p2=Point(0,(-c-a)/b);
        }
    }
};
struct Circle{
    Point c;
    double r;
    Circle(){}
    Circle(Point  c,double r):c(c),r(r){}
    Circle(double x,double y,double _r){c=Point(x,y);r=_r;}
};
double dpl(Point p,Line v)
{
    return fabs(Cross(p-v.p1,v.p2-v.p1))/Distance(v.p1,v.p2);
}
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}
double Len2(Vector A){return Dot(A,A);}
Point plp(Point p,Line v)
{
    double k=Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
    return v.p1+(v.p2-v.p1)*k;
}
int lcr(Line v,Circle C)
{
    double dst=dpl(C.c,v);
    if(sgn(dst-C.r)<0)return 0;
    if(sgn(dst-C.r)==0)return 1;
    return 2;
}
double Len(Vector A){return sqrt(Dot(A,A));} 
int lcc(Line v,Circle C,Point &pa,Point &pb)
{
    if(lcr(v,C)==2)return 0;
    Point q=plp(C.c,v);
    double d=dpl(C.c,v);
    double k=sqrt(C.r*C.r-d*d);
    if(sgn(k)==0)
    {
        pa=q;pb=q;return 1;
    }
    Point n=(v.p2-v.p1)/Len(v.p2-v.p1);
    pa=q+n*k;pb=q-n*k;
    return 2;
}


double so(Line ln1, Line ln2){
    Point a;
    Point b;

    a = ln1.p1;
    b = ln1.p2;
    if(a.x > b.x)swap(a, b);
    
    Point e;
    Point f;
    
    e = ln2.p1;
    f = ln2.p2;

    if(e.x > f.x)swap(e, f);    
    
    if(a.x > e.x ){
        swap(a,e); 
        swap(b,f);
    } 
    
//    printf("[so] %.10lf , %10lf\n", a.x, a.y);
//    printf("[so] %.10lf , %10lf\n", b.x, b.y);
//    printf("[so] %.10lf , %10lf\n", e.x, e.y);
//    printf("[so] %.10lf , %10lf\n", f.x, f.y);
//    puts("end");
    
    if(b.x < e.x)return 0;
    if(f.x < b.x)return Distance(f,e);
    return Distance(b,e);
    
}

double so_by_y(Line ln1, Line ln2){
    Point a;
    Point b;

    a = ln1.p1;
    b = ln1.p2;
    if(a.y > b.y)swap(a, b);
    
    Point e;
    Point f;
    
    e = ln2.p1;
    f = ln2.p2;

    if(e.y > f.y)swap(e, f);    
    
    if(a.y > e.y ){
        swap(a,e); 
        swap(b,f);
    } 
    
//    printf("[so] %.10lf , %10lf\n", a.x, a.y);
//    printf("[so] %.10lf , %10lf\n", b.x, b.y);
//    printf("[so] %.10lf , %10lf\n", e.x, e.y);
//    printf("[so] %.10lf , %10lf\n", f.x, f.y);
//    puts("end");
    
    if(b.y < e.y)return 0;
    if(f.y < b.y)return Distance(f,e);
    return Distance(b,e);
    
}

double so_p(Line ln1, Line ln2, Line ln3){
    Point a;
    Point b;

    a = ln1.p1;
    b = ln1.p2;
    if(a.x > b.x)swap(a, b);
    
    Point e;
    Point f;
    
    e = ln2.p1;
    f = ln2.p2;

    if(e.x > f.x)swap(e, f);    
    
    if(a.x > e.x ){
        swap(a,e); 
        swap(b,f);
    } 
    
    if(b.x < e.x)return 0;
    if(f.x < b.x)return so(Line(e,f), ln3);
    return so(Line(e,b), ln3);    
}

double so_p_by_y(Line ln1, Line ln2, Line ln3){
    Point a;
    Point b;

    a = ln1.p1;
    b = ln1.p2;
    if(a.y > b.y)swap(a, b);
    
    Point e;
    Point f;
    
    e = ln2.p1;
    f = ln2.p2;

    if(e.y > f.y)swap(e, f);    
    
    if(a.y > e.y ){
        swap(a,e); 
        swap(b,f);
    } 
    
    if(b.y < e.y)return 0;
    if(f.y < b.y)return so(Line(e,f), ln3);
    return so(Line(e,b), ln3);    
}


signed main(){
    int x,y,r;
    cin >> x >> y >> r;
    Circle c1 = Circle(x,y,r);
    cin >> x >> y >> r;
    Circle c2 = Circle(x,y,r);
    
    int a,b,e,f;
    cin >> a >> b >> e >> f;
    Line ln = Line(Point(a,b), Point(e,f));
    
    Point su_1_1;
    Point su_1_2;
    Point su_2_1;
    Point su_2_2;
    int num_1 = lcc(ln,c1,su_1_1, su_1_2); 
    int num_2 = lcc(ln,c2,su_2_1, su_2_2);
    double su=0;
//    if(num_1 == 2) su += Distance(su_1_1, su_1_2);
//    if(num_2 == 2) su += Distance(su_2_1, su_2_2);
    
    
    Line ln1 = Line(su_1_1,su_1_2);
    Line ln2 = Line(su_2_1,su_2_2);
    if(a == e){
        su = so_by_y(ln1, ln) + so_by_y(ln2, ln) - so_p_by_y(ln1, ln2,ln); 
    }else{
        su = so(ln1, ln) + so(ln2, ln) - so_p(ln1, ln2,ln); 
//        printf("[qwe] %.10lf  %.10lf \n",ln.p2.x, ln.p2.y);
//        printf("[asd] %.10lf  %.10lf  %.10lf\n",so(ln1, ln), so(ln2, ln), so(ln1, ln2));
    }
    
//    cout << su; 
    printf("%.10lf",su);
}

/*
0 0 1 
2 2 1
-1 -1 3 3


0 0 1
1 1 1
0 0 1 1

0 0 1
0 3 1
0 -2 0 5

0 0 1
0 2 1
0 -1 0 3

0 0 1
0 1 1
0 -1 0 3

2 0 2
3 0 2


0 0 1
1 1 1

0 0 2
2 0 2
-1 0 0 0

*/