方法和题解一样但是20分,求救~
查看原帖
方法和题解一样但是20分,求救~
1065103
Atri_Lobato楼主2024/5/21 22:14
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,s;
struct Rail
{
	int left,right;
	int lowest;
	//y="k"x+"b"
	double k,b;
}rail[100005];
int main()
{
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;i++)
	{
		double x1,x2,y1,y2;
		scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
		double k=0,b=0;
		k=(y2-y1)*1.0/(x2-x1);
		b=y1*1.0-k*x1;
		rail[i].k=k;
		rail[i].b=b;
		rail[i].left=min(x1,x2);
		rail[i].right=max(x1,x2);
		rail[i].lowest=min(y1,y2);
	}
	bool flag=1;
	int ans=s,hnow=999999999;
	while(flag)
	{
		flag=0;
		double maxn=-99999999999;
		int the=0;
		for(int i=1;i<=n;i++)
		{
			if(rail[i].left<ans&&ans<rail[i].right&&hnow>=rail[i].lowest)
			{
				double heighth=rail[i].k*ans+rail[i].b;
				if(heighth>maxn)
				{
					maxn=heighth;
					the=i;
					flag=1;
				}
			}
		}
		if(flag==1)
		{
			if(rail[the].k>0)
			{
				ans=rail[the].left;
			}
			else
			{
				ans=rail[the].right;
			}
			hnow=rail[the].lowest;
		}
	}
	cout<<ans;
	return 0;
}
2024/5/21 22:14
加载中...