2019-2020 ICPC, Asia Jakarta Regional Contest H题题解

发表于 |

题目描述：给n个矩形二维容器(xi×yi)，求面积最大的矩形块A×B，使得两个这样的矩形块能塞进容器里。

塞法有两种：塞在同一个容器；塞在两个不同的容器。前一种情况很水，后一种也不难。枚举矩形块的较小边A，这个较小边也必然是某个容器的较小边。所以只要枚举容器的较小边就行了，这样确定第一个容器；然后在第一条边大于A的容器中，找第二条边的最大值。该值与第一个容器的较大边的较小值，就是矩形块的较大边B。

于是问题转换成求区间最大值，方法很多，这里采取排序后倒序枚举解决。

注意double(精度仅52位)存不下答案，要用long double，或者手动处理long long来输出答案。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
 *powered by caibiCH2
 *create at 2019-12-11 17:22:23
 */
#include <bits/stdc++.h>
#define elif else if
//#define max(x,y) ((x)>(y)?(x):(y))
//#define min(x,y) ((x)<(y)?(x):(y))
#define INF 0x3f3f3f3f
typedef long long ll;

using namespace std;
struct msp{
	ll x,y;
	friend bool operator<(const msp&p,const msp&q){
		return p.x<q.x;
	}
}a[3000100];
int main (/*int argc, char const* argv[]*/){
	std::ios::sync_with_stdio(false);
	int n;cin>>n;
	ll ans=0;
	for(int i=1;i<=n;i+=1){
		cin>>a[i].x>>a[i].y;
		ans=max(ans,a[i].x*a[i].y);
		if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
	}
	sort(a+1,a+n+1);
	ll t=0;
	for(int i=n;i>=1;--i){
		ans=max(ans,min(a[i].y,t)*a[i].x*2);
		t=max(t,a[i].y);
	}
	long double kksk=ans;
	kksk/=2;
	cout<<fixed<<setprecision(1)<<kksk<<'\n';
	return 0;
}