「想法题系列」逗比三角形
「题目描述」
小J是一名OI退役滚粗文化课选手，他十分喜欢做题，尤其是裸题。他现在有一个二维盒子和一些二维三角形，这个盒子拥有无限的高度和L的宽度。而且他的三角形也都是一些锐角三角形或者是直角三角形。现在小J想把这些三角形放入盒子里，由于小J从txt大神犇那里学会了魔♂法，所以小J的三角形既可以无视盒子边界又可以重叠放置，但是必须有一条边紧贴盒子底面所在的直线。
现在小J想要最大化在盒子中的被三角形覆盖的区域的面积（即三角形间的重叠部分只算一遍），请问这个最大值应该是多少？
「输入格式」
一行一个整数T，代表数据组数。下面T部分，每部分第一行两个整数N,L分别代表三角形数量与盒子的宽度。下面N行每行三个整数ai,bi,ci表示三角形i的三条边长。
「输出格式」
T行，每行一个实数代表盒子内部被三角形覆盖的区域的面积的最大值。
题解
结论：最短边放在x轴上；放置在x轴上的边确定时，最优解满足所有三角形之间的交点在一条平行于x轴的直线上
证明：
将三角形剖分成宽为d的矩形，从高到低排序，那么我们肯定选择前L/d个矩形放在盒子里最优，那么无限剖分矩形后，假设我们选择的最后一个矩形高度是H，那么对于高度大于H的三角形来说，肯定有一个属于该三角形的高度为H的矩形被选择了。那么对于所有高度大于H的三角形来说，高度为H的部分肯定都放在盒子里了，即交点的高度都是H。
有了上面的结论后，显然，三角形越高越容易被选择，所以三角形应该越高越好。
二分交点高度
|
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<cstdlib> #include<cmath> #include<algorithm> #define eps 1e-5 #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n; double L,ans; double a[100005],b[100005],c[100005]; double h[100005],area[100005]; double cal(double x) { double tmp=0; for(int i=1;i<=n;i++) if(h[i]>x)tmp+=a[i]*(1-x/h[i]); return tmp; } int main() { T=read(); while(T--) { ans=0; n=read();L=read(); for(int i=1;i<=n;i++) a[i]=read(),b[i]=read(),c[i]=read(); for(int i=1;i<=n;i++) { double p=(a[i]+b[i]+c[i])/2.0; area[i]=sqrt(p*(p-a[i])*(p-b[i])*(p-c[i])); h[i]=area[i]*2/a[i]; } double l=0,r=1000000,mid; while(l+eps<r) { mid=(l+r)/2.0; if(cal(mid)<=L)r=mid; else l=mid; } for(int i=1;i<=n;i++) if(h[i]>mid)ans+=a[i]*(1-mid/h[i])*(h[i]-mid)/2; printf("%.6lf\n",ans+L*mid); } return 0; } |
Subscribe
计数器 9786101
OI 课件=>
OI 课件=>