自动搬运

查看原文

来自洛谷，原作者为

	传奇英雄 鞠躬尽瘁，让bug死而后已

搬运于2025-08-24 21:58:24，当前版本为作者最后更新于2020-05-01 19:47:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

听说是计算几何？看这数据范围，N<=10,T<=100，一股模拟的味道~

我用模拟A了哈哈哈哈

但是，不建议大家用模拟完成此题。很容易被卡。（此篇题解不作为标算，但是确实暴力压标算了。）

模拟的思路：将1秒拆成若干秒，然后模拟雨伞的移动。最后将雨伞位置的左右端点存入pair，排序，求出每一时刻挡住雨的体积。

#include<bits/stdc++.h>
using namespace std;
const int g=12;
int n,w,t,v,type;
double x[g],y[g],z[g],m,r,ans,d;
pair<double,double> a[g];

int main()
{
	//freopen("in","r",stdin);
	scanf("%d%d%d%d",&n,&w,&t,&v);
	type=n*t;//很容易卡精度！所以要根据数据范围选择不同的d
	if(type>500) d=0.00005;
	else
		if(type>200) d=0.000025;
		else d=0.000005;//将1秒拆成若干个d秒
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
		if(!x[i]&&y[i]==w)
		{
			printf("0.00");
			return 0;
		}
		y[i]+=x[i];//x，y是雨伞的左右端点
		z[i]*=d;//z是速度，这里乘d，计算出d秒的走过的路程
	}
	for(double k=0;k<t;k+=d)//总共要走完t秒
	{
		for(int i=1;i<=n;i++)
		{
			x[i]+=z[i];
			y[i]+=z[i];//改变左右端点
			if(x[i]<0)
			{
				x[i]=-x[i];
				y[i]+=x[i]*2;
				z[i]=-z[i];//碰到左边界要返回
			}
			if(y[i]>w)
			{
				m=(y[i]-w)*2;//超出边界的距离要退回去
				y[i]-=m;
				x[i]-=m;
				z[i]=-z[i];//碰到右边界要返回
			}
			a[i].first=x[i];
			a[i].second=y[i];//左右端点存入pair
		}
		sort(a+1,a+n+1);
		m=r=0;//这里m为此刻能挡的雨的体积
		for(int i=1;i<=n;i++)
		{//排序后扫描一遍即可算出m
			if(a[i].first>r)
				r=a[i].first;
			if(a[i].second>r)
			{
				m+=a[i].second-r;
				r=a[i].second;
			}
		}
		ans+=m;//累计答案
	}
	printf("%.2f",v*(w*t-ans*d));//要求的答案是落在马路上的雨
	return 0;
}

最后强调！模拟不是本题正解！很容易卡！如果用模拟通过了这个题，建议用计算几何重写一遍。