蒟蒻10分求助
  • 板块P1663 山
  • 楼主wzh041500
  • 当前回复10
  • 已保存回复10
  • 发布时间2023/8/8 21:08
  • 上次更新2023/11/3 05:06:16
查看原帖
蒟蒻10分求助
948963
wzh041500楼主2023/8/8 21:08
#include<bits/stdc++.h>
using namespace std;
struct node{
	double x,y;
}sh[5000];
int n;
bool pan(int yy)
{
	double l=0,r=100000; 
	for(int i=1;i<n;i++)
	{
		if(sh[i].y==sh[i+1].y)
		{
			if(yy<sh[i].y)return 0;
		}
		else
		{
			if(sh[i].y>sh[i+1].y)
			{
				l=(sh[i+1].x-sh[i].x)*(yy-sh[i].y)/(sh[i+1].y-sh[i].y)+sh[i].x;
				if(l>r)return 0;
			}
			else
			{
				r=(sh[i+1].x-sh[i].x)*(yy-sh[i].y)/(sh[i+1].y-sh[i].y)+sh[i].x;
				if(l>r)return 0;
			}
		}
	//	cout<<l<<" "<<r<<" ";
	}
	return 1;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>sh[i].x>>sh[i].y;
	}
	double l=0,r=1000000,mid,ans=-1;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(pan(mid))
		{
			r=mid-0.001;
			ans=mid;
		}
		else
		{
			l=mid+0.001;
		}
	}
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
}
样例过了,提交只得了10分,
2023/8/8 21:08
加载中...