8
30
2015
7

【二分+罗干】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: 1499
cleaning services ab 说:
2021年8月30日 17:21

Urban center Help Cleaning up company is Focused upon high benchmarks of safety and health for a staff, all of our valuable prospects and targeted traffic. No matter how you would consider it, cleaning for your personal house, business, restaurant, or every residential plus commercial space is undoubtedly an important item of the marvel - regardless of the kind with business you will be in or exactly what property you will be living around City Enable provides you an array of commercial plus residential cleaning up services along at the best amount.

part time maids in d 说:
2021年9月27日 14:23

The ideal and even top-notch maintaining expertise on Dubai present productive maintaining and a doorsteps. As a consequence, DIALAMAID can be these that can assist you considering the best accessories and even dependable maintaining programs to confirm a nourishing and even germ-free your kitchen's surrounding. They have perhaps an important power team in maintaining industry professionals that definitely have proficiency on housekeeping services expertise on top of that. On top of that, some people shoot for presenting productive maintaining to help you people. As a result, you need an important hassle-free your kitchen's maintaining product, sign up to DIALAMAID.

monthly cleaning ser 说:
2021年11月15日 22:28

Gurus assist by providing their practical knowledge and encounter to latest franchisees. You will find ongoing support to boot, including has to be the, security not to mention safety strategies, meetings, some toll-free program line, web-based, and particular field operations not to mention evaluations. There can be instructional Video games, a privately owned website, not to mention advanced guidance. Maid Brigade is focusedon making absolutely sure all franchises are actually successfully not to mention profitably jog. The company insures advertising, not to mention sends latest ads not to mention promotions towards each franchise's.

babysitting services 说:
2023年9月11日 20:00

What I will be getting at could be the idea in which price just isn't the simply factor each time a customer determines a color contractor. The greatest excuse My partner and i hear coming from paint installers is which they either drop jobs due to the fact their value is exorbitant or they don't really estimate work correctly.

maid services dubai 说:
2023年10月04日 16:23

We've been living on an age when ever life might be running the best speed. The competition is extremely tough persons work hrs a x 7 that allows you to protect his or her's position. Each of their time might be spent to generate plans not to mention presentations, meeting shoppers and attempting reach stern deadlines. Hence the residential chores are actually either departed incomplete possibly not undertaken.


登录 *


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