8
30
2015
1

【二分+罗干】Fitting boxes[Codeforces KTU Programming Camp (Day 2) Aug/30/2015 ]

CF传送门

人话:

两个长宽为整数的矩形,判断它们是否能包含。

思维姿势:一定是面积大的包含面积小的矩形(如果包含)。

假设面积小的矩形X长宽AB,面积大的矩形Y长宽CD。

大胆假设当X的三点都在Y上时,第四个点能决定了X能否“缩”在Y内。

枚举情况,并二分X“卡”在Y内的各种角度,判断第四个点是否在Y内。

真·罗干!

Code:

#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
double _90=atan(1.0)*2;
double eps=1e-7;
double eps2=1e-3;
double f(double A,double B,double a)
{
	return sin(a)*A+cos(a)*B;
}
double qia(double A,double B,double C,double l,double r)
{
	if (f(A,B,l)<f(A,B,r))
	{
		while (r-l>=eps)
		{
			double mid=(l+r)/2.0;
			if (f(A,B,mid)<C) l=mid;
			else r=mid;
		}
		if (f(A,B,l)<=C+eps2)return l;
		else return -1;
	}
	else
	{
		while (r-l>=eps)
		{
			double mid=(l+r)/2.0;
			if (f(A,B,mid)<C) r=mid;
			else l=mid;
		}
		if (f(A,B,l)<=C+eps2)return l;
		else return -1;
	}
}
int check(double A,double B,double C,double D)//A,B小 
{
	double m=atan(A/B);
	double a1=qia(A,B,C,0,m);
	if (a1!=-1) if (f(B,A,a1)<=D) return 1;
	double a2=qia(A,B,C,m,_90);
	if (a2!=-1) if (f(B,A,a2)<=D) return 1;
	a1=qia(A,B,D,0,m);
	if (a1!=-1) if (f(B,A,a1)<=C) return 1;
	a2=qia(A,B,D,m,_90);
	if (a2!=-1) if (f(B,A,a2)<=C) return 1;
	return 0;
}
int main()
{
	double A,B,C,D;
	while (1)
	{
		scanf("%lf%lf%lf%lf",&A,&B,&C,&D);
		if (check(A,B,C,D)||check(C,D,A,B)) puts("Yes");
		else puts("No");
	}
	return 0;
}
Category: Codeforces | Tags: 二分 几何 | Read Count: 588

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com