C++(g++ 7.5.0) 解法, 执行用时: 23ms, 内存消耗: 588K, 提交时间: 2022-11-24 14:19:54

#include<bits/stdc++.h>
using namespace std;
typedef double db;
const db pi=acos(-1),eps=1e-8;
struct P{db x,y;};
vector<P>v;
P Head,Foot,Inse,Vert;
db ans;
int n,cur,m;
bool equ(P a,P b){
	return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
}
db dis(P a,P b){
	db dx=a.x-b.x,dy=a.y-b.y;
	return sqrt(dx*dx+dy*dy);
}
int main(){
	scanf("%d",&n);
	v.push_back((P){-100000,0}),v.push_back((P){0,0});
	for(int i=1;i<=n;i++){
		db x,y;scanf("%lf%lf",&x,&y);
		v.push_back((P){x,y});
	}
	m=v.size()-1,cur=m;
	Inse=Foot=(P){v.back().x,v.back().y};
	Head=(P){v.back().x,v.back().y+1};
	for(;;){
		if(Head.y<eps)break;
		db len;bool flg;
		if(equ(Head,Inse))len=1,flg=0,Vert=Foot;
		else if(equ(Foot,Inse))len=1,flg=1,Vert=Head;
		else if(Head.x<Foot.x)len=dis(Head,Inse),flg=1,Vert=Head;
		else len=dis(Foot,Inse),flg=0,Vert=Foot;
		db lw=pi*4;P nInse;
		db r=atan2(Vert.y-Inse.y,Vert.x-Inse.x);
		int pos;
		for(int i=1;i<cur;i++){
			db d=dis(v[i],Inse);
			if(d<len+eps){
				db vr=atan2(v[i].y-Inse.y,v[i].x-Inse.x);
				db add=vr-r;if(add<0)add+=2*pi;
				if(add<lw)lw=add,nInse=v[i],pos=i;   
			}
		}
		for(int i=1;i<=cur;i++){
			db xx,yy;
			db k=(v[i].y-v[i-1].y)/(v[i].x-v[i-1].x);
			db b=v[i].y-v[i].x*k;
			if(k>eps){
				db K=-1/k;
				db B=Inse.y-Inse.x*K;
				xx=(B-b)/(k-K),yy=k*xx+b;
			}else xx=Inse.x,yy=0;
			db Dis=dis((P){xx,yy},Inse);
			if(Dis>len+eps)continue;
			db t=sqrt(len*len-Dis*Dis);
			db R=atan2(v[i-1].y-v[i].y,v[i-1].x-v[i].x);
			db X=xx+cos(R)*t,Y=yy+sin(R)*t;
			if(X<v[i-1].x-eps||X>v[i].x+eps)continue;
			db vr=atan2(Y-Inse.y,X-Inse.x);
			db add=vr-r;if(add<0)add+=2*pi;
			if(add<lw)lw=add,nInse=(P){X,Y},pos=i;
		}
		ans+=lw*dis(Inse,Head);
		if(!equ(Head,Inse)){
			db t=dis(Inse,Head);
			db rh=atan2(Head.y-Inse.y,Head.x-Inse.x)+lw;
			Head.x=Inse.x+cos(rh)*t;
			Head.y=Inse.y+sin(rh)*t;
		}
		if(!equ(Foot,Inse)){
			db t=dis(Inse,Foot);
			db rh=atan2(Foot.y-Inse.y,Foot.x-Inse.x)+lw;
			Foot.x=Inse.x+cos(rh)*t;
			Foot.y=Inse.y+sin(rh)*t;
		}
		Inse=nInse,cur=pos;
	}
	printf("%.8lf",ans);
}

C++ 解法, 执行用时: 23ms, 内存消耗: 532K, 提交时间: 2022-06-18 19:47:18

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define eb emplace_back

using namespace std;
using pt = complex<double>;

const int N = 1000 + 5;
const double PI = acos(-1), eps = 1e-9;

int n;
pt a[N];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	double x, y;
	rep(i, 2, n + 1) cin >> x >> y, a[i] = {x, y};
	a[0] = {-2, 0};
	pt nw(x, y);
	double an = -PI / 2, len = 1, ans = 0;
	bool head = 0;
	while(!head || nw.imag() > eps) {
		vector<pair<pt, double>> v;
		auto find = [&](const pt& a, const pt& b) {
			double l = 0, r = 1;
			rep(kase, 1, 45) {
				double mid = (l + r) / 2;
				(abs(nw - mid * a - (1 - mid) * b) >= len ? r : l) = mid;
			}
			pt tmp(l * a + (1 - l) * b);
			v.eb(tmp, arg(tmp - nw));
		};
		bool can = 1;
		rep(i, 1, n + 1) if(a[i].real() < nw.real() - eps) {
			if(abs(a[i] - nw) <= len) {
				v.eb(a[i], arg(a[i] - nw));
				if(can) find(a[i - 1], a[i]), can = 0;
			}
		} else { if(can) find(a[i - 1], nw); break; }
		double mn = 10;
		for(auto [p, a] : v) mn = min(mn, a);
		pt nxt(1000, 1000);
		for(auto [p, a] : v) if(a < mn + eps && p.real() < nxt.real()) nxt = p;
		bool f = head != (len == 1);
		ans += fmod(mn - an + f * PI + PI * 4, PI * 2) * (f ? len : 1 - len);
		an = f * PI + mn, head ^= len == 1;
		len = abs(abs(nxt - nw) - len) < eps ? 1 : len - abs(nxt - nw), nw = nxt;
	}
	printf("%.6lf", ans);
}