UVA 10652 Board Wrapping(凸包求面积)
题意:
有n块矩形木板,你的任务是用一个面积尽量小的凸多边形把它们包起来,并计算木板占整个包装面积的百分比.
分析:
刘汝佳<<训练指南>> P272例题6
给出了每个木板的中心和长,宽以及旋转角度,通过先旋转向量然后把中心点平移对应的向量可以求出矩形的4个顶点坐标.
然后我们根据矩形的所有顶点求出凸包,并求出凸包的面积.(即总面积)
最后用所有矩形的面积和/总面积就是百分比了.
AC代码:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-10;
const double PI=acos(-1);
int dcmp(double x)
{
if(fabs(x)<eps) return 0;
return x<0?-1:1;
}
struct Point
{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
bool operator<(const Point &B)const
{
return dcmp(x-B.x)<0 || (dcmp(x-B.x)==0 && dcmp(y-B.y)<0 );
}
bool operator==(const Point &B)const
{
return dcmp(x-B.x)==0 && dcmp(y-B.y)==0;
}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
return Vector(A.x-B.x,A.y-B.y);
}
Vector operator+(Vector A,Vector B)
{
return Vector(A.x+B.x,A.y+B.y);
}
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
Vector Rotate(Vector A,double rad)
{
return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
double PolygonArea(Point *p,int n)
{
double area=0;
for(int i=1;i<n-1;++i)
area += Cross(p[i]-p[0],p[i+1]-p[0]);
return fabs(area)/2;
}
int ConvexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
n=unique(p,p+n)-p;
int m=0;
for(int i=0;i<n;++i)
{
while(m>1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-1])<=0 ) --m;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--)
{
while(m>k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-1])<=0) --m;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
const int maxn=600*4+10;
Point p[maxn];
int cnt;//点数目
int main()
{
int T; scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
cnt=0; //当前点数目
double area1=0;//矩形面积和
while(n--)
{
double x,y,w,h,j;
scanf("%lf%lf%lf%lf%lf",&x,&y,&w,&h,&j);
area1 += w*h;
Point o(x,y); //矩形中心点
double rad=-(j/180*PI); //角度转弧度
p[cnt++]=o+Rotate(Vector(w/2,h/2), rad);
p[cnt++]=o+Rotate(Vector(-w/2,h/2), rad);
p[cnt++]=o+Rotate(Vector(w/2,-h/2), rad);
p[cnt++]=o+Rotate(Vector(-w/2,-h/2), rad);
}
Point q[maxn];
cnt=ConvexHull(p,cnt,q);
double area2=PolygonArea(q,cnt);//凸包总面积
printf("%.1lf %%\n",area1*100/area2);
}
return 0;
}
分享到:
相关推荐
探求二维凸包及其应用,许瑞广,余志伟,凸包是计算几何中最普遍、最基本的一种结构,本文介绍了二维凸包的概念和性质,并介绍几种求二维凸包的方法:Gift-Wrapping、Graham-Scan�
我个人用java写的关于凸包的JarvisMarch算法,也称gift wrapping算法。比较完美,算法的实现很简洁,只有加减乘除的基本运算,程序运行效率很高,计算10万个点的运行时间大概20秒左右。适当增加Point类中的屏幕范围...
Dynamic Time Wrapping的源代码
WrappingViewPager ViewPager replacement with dynamic height support and smooth animations ... compile 'com.github.iffa:wrapping-viewpager:1.10' } Quick start Integrating the library takes less than f
曲波变换程序代码,实现图像的曲波分解以及显示,可以去图像进行曲波去噪增强,对彩色图像空间模型转化后提取曲波信息
fdct_wrapping_dispcoef - 返回一个包含所有图像曲波系数的图象
该项目解决了并行化三种凸包算法的目标:Quickhull、Gift Wrapping 和 Graham Scan。 ##许可所有源代码(HeavySort 除外)-版权所有 Kapil Gowru、Mathew Kurian 和 Ankit Tandon HeavySort - 版权所有罗斯安德森 ...
wrapping curvelet demos in matlab
AesKeyWrappingKey2019加密套件上下文存储库(aes-key-wrapping-2019-context) 适用于JavaScript的AesKeyWrappingKey2019加密套件的JSON-LD上下文。 目录 背景 另请参阅(相关规格): 安装 需要Node.js 12+ 要...
In situ wrapping of the cathode material in lithium-sulfur batteries
connectors make it possible to easily connect a daughter board or wrapping board for a specific application. This user manual provides information on using the STM3210B-EVAL board and its hardware ...
Unity Premium Learn Course -Advance Programming - Closing the Loop 完整资源。这个资源基本上是剑铲示例游戏的最终版了。
Swift-API-Wrapping 带闭包的基本 API 包装类(支持 Alamofire) 例子 APIWrapping.sharedManager.get("get", params: nil, success: { (responseObject) -> Void in println(responseObject) // Wrap JSON result ...
Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、...
curvelet generation subprogram
字符串::包装 用全角字符和ANSI代码包装字符串。... strings = Strings :: Wrapping . new strings . wrap ( "It is not down on any map; true places never are." , 20 ) # => "It is not down on\nany map; true p
在Python中包装自定义VTK类的独立测试/示例。 两者都可以一劳永逸地弄清楚这一点,并在将来有一些参考。 基于VTK 6.2(和OpenGL2模块) CMake命令是从不同的来源和示例中拼凑而成的,例如 来自vtk用户列表的帮助
Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、...
作者iffa,源码wrapping-viewpager,viewpage替换与动态的高度支持和平滑的动画标准,viewpage的为数不多的边界情况不满足您的需要。