洛谷题目传送门

CF题目传送门

对于这题，我无力吐槽。

虽然式子还是不难想，做法也随便口胡，但是一些鬼畜边界情况就是判不对。

首先显然二分答案。

对于每一个雨滴，它出现的时刻我们的绳子必须落在它上面。把绳子的上下端点用二元组\((a,b)\)表示，因为三个点\((a,0)(x_i,y_i)(b,h)\)共线，我们可以推出

这说明了\(a,b\)的关系，必须落在一条直线上！它在\((0,0)(0,w)(w,w)(w,0)\)矩形范围内的部分就是可行域。

现在，我们初始的可行域是一个点\((e1,e2)\)，到下一个时刻之前，可行域会向四周扩散\(v*\Delta t\)个单位，形成了一个正方形。这个正方形与下一个可行域线段的交，就是当前真正的可行域。那假如当前可行域是一个线段，它扩散是什么样子呢？是一个六边形，等于线段和正方形的闵可夫斯基和。

一个线段和一个凸包的交怎么求呢？我的做法比较蒟蒻，把线段和凸包的交点求出来，按交点个数、端点与凸包的位置关系分类讨论一下。

我们不断地做下去，中途如果出现可行域没有交了就说明不合法。

接下来是实现细节。

首先，对于\(t\)相同的雨滴，我们直接把它们的可行域合并，以免接下来做闵可夫斯基和的时候凸包退化成点或线段。

头疼的就是这里了。合并的时候，要分成线段和线段的交，线段和点的交，点和点的交讨论个半天。因为线段和线段可以直接套SegCross求交点，但是线段和点不能套，会除\(0\)。注意线段平行/重合还要单独拿出来判，不过显然如果重合的话\(x,y\)都是相等的，不然就平行也就是没有交集了，直接cout<<"-1"。

再就是特判的时候有些地方非得用EPS，不然过不了。因为值域为整数而且范围只有\(10^3\)，所以EPS设大点没关系，小于\(\frac{1}{\text{值域}^2}\)就可以了。

惨痛的教训：强烈建议不要试图将此题作为计算几何板子的练习题，因为光是讨论就不知道比敲板子麻烦到哪里去了。有些丑陋的板子看不懂的话就去踩蒟蒻的总结吧。

#include<bits/stdc++.h>

#define R register int

#define I inline

#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))

using namespace std;

typedef double DB;

const int SZ=1<<19,N=1e5+9;

const DB EPS=1e-8;

char buf[SZ],*ie=buf+SZ,*ip=ie-1;

inline int in(){

	G;while(*ip<'-')G;

	R x=*ip&15;G;

	while(*ip>'-'){x*=10;x+=*ip&15;G;}

	return x;

}

inline bool is0(DB x){return fabs(x)<EPS;}

struct Vec{

	DB x,y;

	I Vec(){x=y=0;}

	I Vec(DB a){x=a;y=0;}

	I Vec(DB a,DB b){x=a;y=b;}

	I friend istream&operator>>(istream&cin,Vec&a){return a.x=in(),a.y=in(),cin;}

	I Vec operator-(){return Vec(-x,-y);}

	I Vec operator+(Vec a){return Vec(x+a.x,y+a.y);}

	I Vec operator-(Vec a){return Vec(x-a.x,y-a.y);}

	I Vec operator*(DB a){return Vec(x*a,y*a);}

	I Vec operator/(DB a){return Vec(x/a,y/a);}

	I friend Vec operator*(DB a,Vec b){b.x*=a,b.y*=a;return b;}

	I Vec&operator+=(Vec a){x+=a.x,y+=a.y;return*this;}

	I Vec&operator-=(Vec a){x-=a.x,y-=a.y;return*this;}

	I DB operator*(Vec a){return x*a.x+y*a.y;}

	I DB operator^(Vec a){return x*a.y-y*a.x;}

	I bool operator==(Vec a){return is0(x-a.x)&&is0(y-a.y);}

	I friend bool operator<(Vec a,Vec b){

		return (a^b)>0||(is0(a^b)&&Len(a)<Len(b));

	}

	I friend DB Len(Vec a){

		return sqrt(a.x*a.x+a.y*a.y);

	}

}a[N],b[N],c[9],d[9],e;

int t[N],st[N];

I Vec LineCross(Vec a1,Vec a2,Vec b1,Vec b2){

	a2-=a1;b2-=b1;

	return b2^a2?a1+(b2^(b1-a1))/(b2^a2)*a2:Vec(NAN,NAN);

}

I Vec SegCross(Vec&a1,Vec&a2,Vec&b1,Vec&b2){

	Vec c=LineCross(a1,a2,b1,b2);

	return (a1-c)*(a2-c)>EPS||(b1-c)*(b2-c)>EPS?Vec(NAN,NAN):c;

}

I int Convex(Vec*a,R n){

	R k=0,p=0;Vec bs;

	for(R i=1;i<n;++i)

		if(a[i].y<a[k].y||(a[i].y==a[k].y&&a[i].x<a[k].x))k=i;

	swap(a[0],a[k]);bs=a[0];

	for(R i=0;i<n;++i)a[i]-=bs;

	sort(a+1,a+n);

	for(R i=1;i<n;st[++p]=i++)

		while(p&&((a[i]-a[st[p-1]])^(a[st[p]]-a[st[p-1]]))>-EPS)--p;

	for(R i=0;i<=p;++i)a[i]=a[st[i]]+bs;

	return a[p+1]=bs,p+1;

}

I int Minkowski(Vec*a,R n,DB t){

	for(R i=n-1,j=4*n;j;--i){

		a[--j]=a[i]+Vec(-t,-t);

		a[--j]=a[i]+Vec( t,-t);

		a[--j]=a[i]+Vec( t, t);

		a[--j]=a[i]+Vec(-t, t);

	}

	return Convex(a,4*n);

}

I bool Inside(Vec*a,R n,Vec v){//点是否在凸包内

	for(R i=0;i<n;++i)

		if(((a[i+1]-a[i])^(v-a[i]))<-EPS)return 0;

	return 1;

}

I bool Check(R q,DB mid){

	R n=1,p;

	c[0]=e;

	for(R i=1;i<=q;++i){

		n=Minkowski(c,n,(t[i]-t[i-1])*mid);

		for(R j=p=0;j<n;++j){//搞出所有交点，注意去重

			d[p]=SegCross(a[i],b[i],c[j],c[j+1]);

			p+=!(isnan(d[p].x)||(p&&d[p-1]==d[p]));

		}

		if(p==0){//更新当前可行域，讨论开始

			if(!Inside(c,n,a[i]))return 0;

			c[0]=a[i],c[1]=b[i];

		}

		else if(p==1){

			if(Inside(c,n,a[i]))

				c[1]=Inside(c,n,b[i])?(d[0]==b[i]?a[i]:b[i]):a[i];

			else c[1]=Inside(c,n,b[i])?b[i]:d[0];

			c[0]=d[0];

		}

		else c[0]=d[0],c[1]=d[1];//讨论结束

		n=1+!(c[0]==c[1]);

	}

	return 1;

}

I void Err(bool f){if(f)cout<<"-1\n",exit(0);}

int main(){

	ios::sync_with_stdio(0);

	R n=in(),q=0,w=in(),h=in(),lx=0,ly=0;

	cin>>e;

	for(R i=1;i<=n;++i){

		R tt=in(),x=in(),y=in();

		Vec u=0,v=0;//求可行域线段，讨论开始

		if((u.x=(DB)x*h/(h-y))>w)u=Vec(w,(DB)(x*h-(h-y)*w)/y);

		if((v.y=(DB)x*h/y    )>w)v=Vec((DB)(x*h-y*w)/(h-y),w);//讨论结束

		if(tt!=t[q])++q,a[q]=u,b[q]=v;//合并t相同的可行域，讨论开始

		else if(a[q]==b[q]){

			if(u==v)Err(!(u==a[q]));//点交点

			else Err(!is0((u-a[q])^(v-a[q])));//点交线段

		}

		else if(x!=lx||y!=ly){

			if(u==v)Err(!is0((u-a[q])^(u-b[q])));//点交线段

			else Err(isnan((u=SegCross(a[q],b[q],u,v)).x));//线段交线段

			a[q]=b[q]=u;

		}//讨论结束

		t[q]=tt;lx=x;ly=y;

	}

	DB l=0,r=w,mid;

	while((r-l)/max(1.0,l)>1e-4)

		mid=(l+r)/2,(Check(q,mid)?r:l)=mid;

	cout<<fixed<<setprecision(6)<<(l+r)/2<<'\n';

	return 0;

}