F灯下定影

求出直线与圆的交点之后问题转为n个区间的并集

#include <cstdio>
#include <math.h>
#include<algorithm>
using namespace std;
#define COUNTER_CLOCKWISE -1 //逆时针
#define CLOCKWISE 1          //顺时针
#define ONLINE_BACK -2       //p2 p0 p1依次排列在一条直线上
#define ONLINE_FRONT 2       //p0 p1 p2依次排列在一条直线上
#define ON_SEGMENT 0         //p2在线段p0p1上
#define EPS 1E-8
class Point
{
public:
	double x, y;
	Point()
	{
	}
	Point(double x, double y)
	{
		(*this).x = x;
		(*this).y = y;
	}
	
	double operator^(const Point &p) const //叉乘
	{
		return x * p.y - y * p.x;
	}
	
	double operator*(const Point &p) const //点乘
	{
		return x * p.x + y * p.y;
	}
	
	Point operator*(const double &d) const
	{
		return Point(x * d, y * d);
	}
	
	Point operator/(const double &d) const
	{
		return Point(x / d, y / d);
	}
	
	Point operator-(const Point &p) const
	{
		return Point(x - p.x, y - p.y);
	}
	
	Point operator+(const Point &p) const
	{
		return Point(x + p.x, y + p.y);
	}
	
	double sqr()
	{
		return x * x + y * y;
	}
	double abs()
	{
		return sqrt(sqr());
	}
	
	double distance(const Point &p)
	{
		return fabs((*this - p).abs());
	}
	
	void print()
	{
		
		printf("%.8lf %.8lf", x, y);
	}
};

class Line
{
public:
	Point p1, p2;
	Point vec;
	Line()
	{
	}
	Line(Point p1, Point p2)
	{
		(*this).p1 = p1;
		(*this).p2 = p2;
		(*this).vec = p2 - p1;
	}
};

class Circle
{
public:
	Point o;
	double r;
	Circle()
	{
	}
	
	Circle(Point o, double r)
	{
		(*this).o = o;
		(*this).r = r;
	}
	
	Circle(double cx, double cy, double r)
	{
		(*this).o.x = cx;
		(*this).o.y = cy;
		(*this).r = r;
	}
};

double get_distance_LP(const Line &line, const Point &p) //点到直线的距离
{
	return fabs((p - line.p1) ^ (line.p1 - line.p2) / (line.p1 - line.p2).abs());
}

pair<Point, Point> get_Cross_Points(Circle c, Line l)
{
	//l.p1.print();
	Point pr = l.p1 + (l.vec) * ((c.o - l.p1) * l.vec)/ ( l.vec.sqr());
	
	double base = sqrt(c.r * c.r - (pr-c.o).sqr());
	if (base <= EPS) //只有一个交点
	{
		return make_pair(pr, pr);
	}
	
	//有两个交点
	Point e = (l.vec) / l.vec.abs();
	
	return make_pair(pr + e * base, pr - e * base);
}
struct node{
	double st,ed;
}aa[1000000];
bool cmp(node a,node b){
	return a.st<b.st;
}
int main()
{
	double x0,y0,r;
	cin>>x0>>y0>>r;
	Circle c(x0, y0, r);
	Point c0(x0,y0);
	int n;
	double k;
	cin>>n>>k;
	
	for(int i=1;i<=n;i++){
		Line l  = Line();
		cin >> l.p1.x >> l.p1.y >> l.p2.x >> l.p2.y;
		l.vec = l.p2-l.p1;
		double sd;
		cin>>sd;
		if(get_distance_LP(l,c0)>r){
			aa[i].st=0;
			aa[i].ed=0;
			continue;
		}
		int boo1=0,boo2=0;
		auto ans = get_Cross_Points(c, l);
		if(ans.first.x-l.p1.x>0){
			boo1=1;
		}
		if(l.p2.x-l.p1.x>0){
			boo2=1;
		}
		if(boo1!=boo2){
			aa[i].st=0;
			aa[i].ed=0;
			continue;
		}
		double sj1=l.p1.distance({ans.first.x,ans.first.y})/sd;
		double sj2=l.p1.distance({ans.second.x,ans.second.y})/sd;
		if(sj1<sj2){
			aa[i].st=sj1;
			aa[i].ed=sj2+k;
		}
		else{
			aa[i].st=sj2;
			aa[i].ed=sj1+k;
		}
	}
	sort(aa+1,aa+n+1,cmp);
	aa[n+1].st=100000000;
	aa[n+1].ed=100000000;
	double ans=0;
	double st=0,ed=0;
	for(int i=1;i<=n+1;i++){
		auto [l,r]=aa[i];
		if(l>ed||i==n+1||i==1){
			ans+=ed-st;
			st=l;
			ed=r;
		}
		else{
			if(r>ed) ed=r;
		}
	}
	printf("%.16lf\n",ans);
	
}