蓝桥杯-车轮轴迹

Posted on | In | Views:

题意

img

求圆心轨迹的总长度。

题解

圆有两种状态，一是在线段上，二是在端点上。平移或旋转时可能会被线段阻挡，也可能会被端点阻挡。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
#include <bits/stdc++.h>
using namespace std;
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forr(i, r, l) for (int i = r; i >= l; i--)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define fro1(i, n) for (int i = 1; i <= n; i++)
#define for0(i, n) for (int i = 0; i < n; i++)
#define fro0(i, n) for (int i = 0; i < n; i++)
#define meminf(a) memset(a, inf, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define memcp(a,b) memcpy(a,b,sizeof(b))
#define oper(type) bool operator <(const type Y)const
#define mp make_pair
#define pu_b push_back
#define pu_f push_front
#define po_b pop_back
#define po_f pop_front
#define fi first
#define se second
typedef pair<long long, long long> pll;
typedef vector<long long> vll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef vector<int> vii;
typedef double db;
typedef long double ldb;
typedef long long ll;
void in(initializer_list<int*> li){for(auto ptr=li.begin();ptr!=li.end();ptr++)scanf("%d",*ptr);}
void in(initializer_list<ll*> li){for(auto ptr=li.begin();ptr!=li.end();ptr++)scanf("%lld",*ptr);}
void in(initializer_list<db*> li){for(auto ptr=li.begin();ptr!=li.end();ptr++)scanf("%lf",*ptr);}
void out(initializer_list<int> li){auto ti=li.end();ti--;for(auto ptr=li.begin();ptr!=li.end();ptr++)printf("%d%c",*ptr,ptr==ti?'\n':' ');}
void out(initializer_list<ll> li){auto ti=li.end();ti--;for(auto ptr=li.begin();ptr!=li.end();ptr++)printf("%lld%c",*ptr,ptr==ti?'\n':' ');}
void out(initializer_list<db> li){auto ti=li.end();ti--;for(auto ptr=li.begin();ptr!=li.end();ptr++)printf("%f%c",*ptr,ptr==ti?'\n':' ');}
void out(int a,bool ln){printf("%d%c",a,ln?'\n':' ');}
void out(ll a,bool ln){printf("%lld%c",a,ln?'\n':' ');}
void out(db a,int digit,bool ln){printf("%.*f%c",digit,a,ln?'\n':' ');}
void out(ldb a,int digit,bool ln){printf("%.*Lf%c",digit,a,ln?'\n':' ');}
void out0(int a[],int n){for0(i,n)out(a[i],i==n-1);}
void out1(int a[],int n){for1(i,n)out(a[i],i==n);}
void out0(ll a[],int n){for0(i,n)out(a[i],i==n-1);}
void out1(ll a[],int n){for1(i,n)out(a[i],i==n);}
int in(int &a,int &b,int &c,int &d){return scanf("%d%d%d%d",&a,&b,&c,&d);}
int in(int &a,int &b,int &c){return scanf("%d%d%d",&a,&b,&c);}
int in(int &a,int &b){return scanf("%d%d",&a,&b);}
int in(ll &a,ll &b,ll &c,ll &d){return scanf("%lld%lld%lld%lld",&a,&b,&c,&d);}
int in(ll &a,ll &b,ll &c){return scanf("%lld%lld%lld",&a,&b,&c);}
int in(ll &a,ll &b){return scanf("%lld%lld",&a,&b);}
int in(ll &a){return scanf("%lld",&a);}
int in(int &a){return scanf("%d",&a);}
int in(char *s){return scanf("%s",s);}
int in(char &c){return scanf("%c",&c);}
int in(db &a){return scanf("%lf",&a);}
int in(ldb &a){return scanf("%Lf",&a);}
void in0(int a[],int n){for0(i,n)in(a[i]);}
void in1(int a[],int n){for1(i,n)in(a[i]);}
void in0(ll a[],int n){for0(i,n)in(a[i]);}
void in1(ll a[],int n){for1(i,n)in(a[i]);}
const db pi = acos(-1);
const db eps = 1e-8;
int sign(db a) {return a < -eps ? -1 : a > eps;}
int db_cmp(db a, db b){ return sign(a-b);}
int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}// k3 在 [k1,k2]或[k2,k1] 内 
ll inf =0x3f3f3f3f;
ll mod = 1e9+7;
const int M = 2.1e5;
const int N = 2.1e5;
/*-----------------------------------head----------------------------------------------*/

struct Point{
    db x,y;
    Point(){}
    Point(db _x,db _y) : x(_x),y(_y){}
    Point operator + (const Point &k1) const{return Point(k1.x+x,k1.y+y);}
    Point operator - (const Point &k1) const{return Point(x-k1.x,y-k1.y);}
    Point operator * (const db k1) const{return Point(x*k1,y*k1);}
    Point operator / (const db k1) const{return Point(x/k1,y/k1);}
    db operator * (const Point b) const{return x * b.x + y * b.y;}//点积
    db operator ^ (const Point b) const{return x * b.y - y * b.x;}//叉积,顺时针为负
    bool operator == (const Point &k1) const{return db_cmp(x,k1.x)==0&&db_cmp(y,k1.y)==0;}
    Point & operator += (const Point &k1) {x+=k1.x;y+=k1.y;return *this;}
    Point & operator -= (const Point &k1) {x-=k1.x;y-=k1.y;return *this;}
    Point & operator *= (const db k1) {*this=*this*k1;return *this;}
    Point & operator /= (const db k1) {*this=*this/k1;return *this;}
    Point rotate(db k1){return Point(x*cos(k1)-y*sin(k1),x*sin(k1)+y*cos(k1));}// 逆时针旋转 
    Point rotate90(){return Point(-y,x);}
    db abs(){return sqrt(x*x+y*y);}
    db abs2(){return x*x+y*y;}
    Point unit(){return *this/abs();}
    db angle(){return atan2(y,x);}
    void out(){printf("%.10f %.10f\n",x,y);}
};
typedef Point Vector;
int inmid(Point k1,Point k2,Point k3){return inmid(k1.x,k2.x,k3.x)&&inmid(k1.y,k2.y,k3.y);}
db angleOfTwoVector(Vector a, Vector b) {return fabs(atan2(a ^ b, a * b));}
Point proj(Point q,Point k1,Point k2){ // q 到直线 k1,k2 的投影 
    Point k=k2-k1;
    return k1+k*((q-k1)*k/k.abs2());
}
Point reflect(Point q,Point k1,Point k2){// q 关于直线 k1,k2 的对称点
    return proj(q,k1,k2)*2-q;
}
Point getLL(Point k1,Point k2,Point k3,Point k4){//直线交点
    db w1=(k1-k3)^(k4-k3),w2=(k4-k3)^(k2-k3);
    return (k1*w2+k2*w1)/(w1+w2);
}
int intersect(db l1,db r1,db l2,db r2){//是否有交集
    if (l1>r1) swap(l1,r1); if (l2>r2) swap(l2,r2); return db_cmp(r1,l2)!=-1&&db_cmp(r2,l1)!=-1;
}
int checkSL(Point k1,Point k2,Point k3,Point k4){// 求线段 (S) k1,k2 和直线 (L) k3,k4 的交点 
    return sign((k3-k1)^(k4-k1))*sign((k3-k2)^(k4-k2))<=0;
}
int checkSS(Point k1,Point k2,Point k3,Point k4){//两线段是否相交
    return intersect(k1.x,k2.x,k3.x,k4.x)&&intersect(k1.y,k2.y,k3.y,k4.y)&&checkSL(k1,k2,k3,k4)&&checkSL(k3,k4,k1,k2);
}
db disPP(Point k1,Point k2){return (k2-k1).abs();}
db disPP2(Point k1,Point k2){return (k2-k1).abs2();}
db disPS(Point q,Point k1,Point k2){
    Point k3=proj(q,k1,k2);
    if (inmid(k1,k2,k3)) return disPP(q,k3); 
    return min(disPP(q,k1),disPP(q,k2));
}
db disPL(Point q,Point k1,Point k2){
    if(k1==k2)return disPP(q,k1);
    return fabs((q - k1) ^ (k2 - k1)) / (k2-k1).abs();
}
db disSS(Point k1,Point k2,Point k3,Point k4){
    if (checkSS(k1,k2,k3,k4)) return 0;
    return min(min(disPS(k1,k3,k4),disPS(k2,k3,k4)),min(disPS(k3,k1,k2),disPS(k4,k1,k2)));
}
db disSL(Point k1,Point k2,Point k3,Point k4){
    if (checkSL(k1,k2,k3,k4)) return 0;
    return min(disPL(k1,k3,k4),disPL(k2,k3,k4));
}
int onS(Point q,Point k1,Point k2){return inmid(k1,k2,q)&&sign((k1-q)^(k2-k1))==0;}

struct Line {
    Point s, t;
    Line(){}
    Line(Point _s,Point _t):s(_s),t(_t){}
    Vector dir(){return (t-s);}
    Vector unitDir(){return (t-s).unit();}
    int place(Point k){return sign((t-s)^(t-k));}
    db len(){return (t-s).abs();}
};
typedef Line Segment;
Point proj(Point q,Line k){return proj(q,k.s,k.t);}
Point reflect(Point q,Line k){return reflect(q,k.s,k.t);}
Point getLL(Line k1,Line k2){return getLL(k1.s,k1.t,k2.s,k2.t);}
bool parallel(Line k1,Line k2){return sign(k1.dir()^k2.dir())==0;}
bool sameDir(Line k1,Line k2){return parallel(k1,k2)&&sign(k1.dir()*k2.dir())==1;}
int checkSS(Segment k1,Segment k2){return checkSS(k1.s,k1.t,k2.s,k2.t);}
int checkSL(Segment k1,Line k2){return checkSL(k1.s,k1.t,k2.s,k2.t);}
db disPS(Point a, Segment b) {return disPS(a,b.s,b.t);}
db disPL(Point a, Line b) {return disPL(a,b.s,b.t);}
db disSS(Segment k1,Segment k2){return disSS(k1.s,k1.t,k2.s,k2.t);}
db disSL(Segment k1,Line k2){return disSL(k1.s,k1.t,k2.s,k2.t);}
int onS(Point q,Segment k){return onS(q,k.s,k.t);}

Point a[N],center;
Line b[N];
db r;
int main() {
    int n;
    db ans=0;
    in(n);
    in(r);
    for0(i,n)in(a[i].x),in(a[i].y);
    center=Point(a[0].x,a[0].y+r);
    for1(i,n-1)b[i]=Segment(a[i-1],a[i]);
    int p=1;
    bool isOnLine=1;
    while(p<=n-1){
        if(isOnLine){
            Vector dir=b[p].dir();
            Vector ver=dir.rotate90().unit();
            Line vli=Line(b[p].s+ver*r,b[p].t+ver*r);
            db k=disPP(center,vli.t);
            isOnLine=0;
            p++;
            for(int i=p;i<n;i++){
                if((vli.dir()^b[i].dir())>0&&disSS(vli,b[i])<r){
                    db tm=disPP(center,getLL(vli,b[i]))-dir.abs()*b[i].dir().abs()*r/abs(dir^b[i].dir());
                    Point t_center=center+vli.dir().unit()*tm;
                    if(db_cmp (disPS(t_center,b[i]),r)==0&&tm<k){
                        k=tm;
                        isOnLine=1;
                        p=i;
                    }
                    if(r-disPS(b[i].t,vli)>-eps){
                        db tmp=disPL(b[i].t,vli)*disPL(b[i].t,vli);
                        db tm=sqrt(disPP2(center,b[i].t)-tmp)-sqrt(r*r-tmp);
                        t_center=center+vli.dir().unit()*tm;
                        if(tm<k&&db_cmp (disPS(t_center,b[i]),r)==0){
                            k=tm;
                            isOnLine=0;
                            p=i+1;
                        }
                    }
                }
            }
            center=center+dir.unit()*k;
            ans+=k;
        }else{
            Point poi=b[p-1].t;
            db k=angleOfTwoVector(b[p].dir().rotate90(),center-poi);
            isOnLine=1;
            for(int i=p+1;i<n;i++){
                Line tm=b[i];
                Vector ver =tm.dir().rotate90().unit()*r;
                tm.s=tm.s+ver;tm.t=tm.t+ver;
                if(r-disPS(poi,tm)>-eps){
                    db ttm=disPL(poi,tm)*disPL(poi,tm);
                    db tmp=sqrt(disPP2(poi,tm.t)-ttm)-sqrt(r*r-ttm);
                    Point t_center=tm.t-tm.dir().unit()*tmp;
                    db tk=angleOfTwoVector(center-poi,t_center-poi);
                    if(tk<k&&db_cmp(disPS(t_center,b[i]),r)==0){
                        k=tk;
                        isOnLine=1;
                        p=i;
                    }
                }
                db tmp=disPP(poi,b[i].t);
                if(2*r-tmp>-eps){
                    tmp=sqrt(r*r-tmp*tmp/4);
                    Point mid=(poi+b[i].t)/2;
                    mid=mid+(b[i].t-poi).rotate90().unit()*tmp;
                    db tk=angleOfTwoVector(center-poi,mid-poi);
                    if(tk<k&&db_cmp(disPS(mid,b[i]),r)==0){
                        k=tk;
                        isOnLine=0;
                        p=i+1;
                    }
                }
            }
            ans+=k*r;
            center=(center-poi).rotate(2*pi-k)+poi;
        }
    }
    out(ans,2,1);
    return 0;
}