Gym - 100520B - 数学

题目链接:https://vjudge.net/problem/Gym-100520B

 

解题思路:

算出每个线段的x区间，那么选择一个区间使得选到这里面达到条件的概率是A，也就是选择区间里的满足条件的长度刚好是总长度*A。因为超过是没意义的。那么也就是枚举l左端点，或者r右端点就行了。枚举l的左端点就是在每段线段的可行区间的左端点，枚举r右端点也就是每段可行的右端点。最后注意线段与x轴平行的情况就行了。

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx = 1e5 + 10;
int n;
double l,r,A;
struct point
{
	double x,y;
}s[mx],p[mx];
typedef point vec; 
double sum[mx];
double GetP(point a,point b,double y)
{
	if(y<=min(a.y,b.y))
	{
		if(a.y<b.y) return a.x;
		return b.x;
	}
	if(y>=max(a.y,b.y)){
		if(a.y<b.y) return b.x;
		return a.x;
	}
	double y0 = a.y - y;
	double y1 = b.y - y;
	return (y1*a.x-y0*b.x)/(y1-y0);
}
double ans,L,R;
void solve1(double m)
{
	double ret = 0;
	int now = 1;
	for(int i=1;i<=n;i++){
		while(now<=n&&ret+p[now].y-p[now].x<m)
		{
			ret += p[now].y-p[now].x;
			now++;
		}
		if(now>n) break;
		double kep = m - ret;
		double fx = p[now].x + kep;
		if(fx-p[i].x<ans){
			ans = fx - p[i].x;
			L = p[i].x,R = fx;
		}
		ret = sum[now-1] - sum[i-1];
		if(now>i) ret -= p[i].y - p[i].x;
		if(now==i) now++;
	}
}
void solve2(double m)
{
	double ret = 0;
	int now = n;
	for(int i=n;i>0;i--){
		while(now&&ret+p[now].y-p[now].x<m)
		{
			ret += p[now].y-p[now].x;
			now--;
		}
		if(now==0) break;
		double kep = m - ret;
		double fx = p[now].y - kep;
		if(p[i].y-fx<ans){
			ans = p[i].y - fx;
			L = fx,R = p[i].y;
		}
		ret = sum[i] - sum[now];
		if(now<i) ret -= p[i].y - p[i].x;
		if(now==i) now--;
	}
}
int main()
{
	freopen("bayes.in ","r",stdin);
	freopen("bayes.out","w",stdout);
	while(scanf("%d",&n)&&n)
	{
		scanf("%lf%lf",&l,&r);
		scanf("%lf",&A);
		for(int i=0;i<=n;i++){
			scanf("%lf%lf",&s[i].x,&s[i].y);
		}
		ans = 1e40;
		double len = 0;
		for(int i=1;i<=n;i++){
			sum[i] = sum[i-1];
			if(s[i].y==s[i-1].y)
			{
				if(l<=s[i].y&&r>=s[i].y){
					p[i].x = s[i-1].x,p[i].y = s[i].x;
					len += s[i].x - s[i-1].x;
					sum[i] += s[i].x - s[i-1].x;
				}
				else p[i].x = p[i].y = s[i].x;
				continue;
			}
			if(r<=min(s[i].y,s[i-1].y)||l>=max(s[i].y,s[i-1].y))
			{
				p[i].x = p[i].y = s[i].x;
				sum[i] = sum[i-1];
				continue;
			}
			p[i].x = GetP(s[i-1],s[i],l);
			p[i].y = GetP(s[i-1],s[i],r);
			if(p[i].x>p[i].y) swap(p[i].x,p[i].y);
			len += p[i].y - p[i].x;
			sum[i] += p[i].y - p[i].x; 
		}
		A *= len;
		solve1(A);
		solve2(A);
		printf("%.8lf %.8lf\n",L,R);
	}
    return 0;
}