The small sawmill in Mission, British Columbia, has
developed a brand new way of packaging boards for
drying. By fixating the boards in special moulds, the
board can dry efficiently in a drying room.
Space is an issue though. The boards cannot be
too close, because then the drying will be too slow.
On the other hand, one wants to use the drying room
efficiently.
Looking at it from a 2-D perspective, your task is
to calculate the fraction between the space occupied by
the boards to the total space occupied by the mould.
Now, the mould is surrounded by an aluminium frame
of negligible thickness, following the hull of the boards’
corners tightly. The space occupied by the mould
would thus be the interior of the frame.
Input
On the first line of input there is one integer, N ≤ 50,
giving the number of test cases (moulds) in the input. After this line, N test cases follow. Each test case
starts with a line containing one integer n, 1 < n ≤ 600, which is the number of boards in the mould.
Then n lines follow, each with five floating point numbers x, y, w, h, ϕ where 0 ≤ x, y, w, h ≤ 10000
and −90◦ < ϕ ≤ 90◦
. The x and y are the coordinates of the center of the board and w and h are the
width and height of the board, respectively. ϕ is the angle between the height axis of the board to the
y-axis in degrees, positive clockwise. That is, if ϕ = 0, the projection of the board on the x-axis would
be w. Of course, the boards cannot intersect.
Output
For every test case, output one line containing the fraction of the space occupied by the boards to the
total space in percent. Your output should have one decimal digit and be followed by a space and a
percent sign (‘%’).
Note: The Sample Input and Sample Output corresponds to the given picture
Sample Input
1
4
4 7.5 6 3 0
8 11.5 6 3 0
9.5 6 6 3 90
4.5 3 4.4721 2.2361 26.565
Sample Output
64.3 %
题解:求矩形面积与凸包面积的比例,顺时针一定要是负....错了半天。。。还有给的ang要转化为rad
代码:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double Pi=acos(-1.0);
struct Point{
double x,y;
Point(double x=,double y=):x(x),y(y){}
};
typedef Point Vector;
bool operator < (Point a,Point b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
double Length(Vector a){return sqrt(Dot(a,a));}
double Angle(Vector a,Vector b){return acos(Dot(a,b)/Length(a)/Length(b));}
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 Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
Point operator + (Point a,Vector b){return Point(a.x+b.x,a.y+b.y);}
Point getdot(Point a,Vector b,double ang){return a+Rotate(b,ang);}
double getrad(double ang){return Pi*(ang/);}
Point ans[],at[];
int nu;
double polygonArea(){
int k=;
for(int i=;i<nu;i++){
while(k>&&Cross(ans[k-]-ans[k-],at[i]-ans[k-])<=)k--;
ans[k++]=at[i];
}
int p=k;
for(int i=nu-;i>=;i--){
while(k>p&&Cross(ans[k-]-ans[k-],at[i]-ans[k-])<=)k--;
ans[k++]=at[i];
}
double x=;
k--;
if(k<)return ;
for(int i=;i<k-;i++)x+=Cross(ans[i]-ans[],ans[i+]-ans[]);
return x/;
}
int main(){
int T,n;
double x,y,w,h,ang;
scanf("%d",&T);
while(T--){
double area1=,area2=;
nu=;
scanf("%d",&n);
while(n--){
scanf("%lf%lf%lf%lf%lf",&x,&y,&w,&h,&ang);
area2+=w*h;
Point a;
ang=-getrad(ang);//因为是顺时针旋转的,所以要是负的。。。。。
at[nu++]=getdot(Point(x,y),Vector(w/,h/),ang);
at[nu++]=getdot(Point(x,y),Vector(-w/,h/),ang);
at[nu++]=getdot(Point(x,y),Vector(w/,-h/),ang);
at[nu++]=getdot(Point(x,y),Vector(-w/,-h/),ang);
}
sort(at,at+nu);
area1=polygonArea();
// printf("%lf %lf\n",area1,area2);
printf("%.1lf %%\n",*area2/area1);
}
return ;
}
UVA 10652 Board Wrapping(凸包)的更多相关文章
-
uva 10652 Board Wrapping (计算几何-凸包)
Problem B Board Wrapping Input: standard input Output: standard output Time Limit: 2 seconds The sma ...
-
UVA 10652 Board Wrapping 计算几何
多边形凸包.. .. Board Wrapping Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu ...
-
简单几何(向量旋转+凸包+多边形面积) UVA 10652 Board Wrapping
题目传送门 题意:告诉若干个矩形的信息,问他们在凸多边形中所占的面积比例 分析:训练指南P272,矩形面积长*宽,只要计算出所有的点,用凸包后再求多边形面积.已知矩形的中心,向量在原点参考点再旋转,角 ...
-
UVA 10652 Board Wrapping(凸包)
题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=32286 [思路] 凸包 根据角度与中心点求出长方形所有点来,然后就 ...
-
Uva 10652 Board Wrapping(计算几何之凸包+点旋转)
题目大意:给出平面上许多矩形的中心点和倾斜角度,计算这些矩形面积占这个矩形点形成的最大凸包的面积比. 算法:GRAHAM,ANDREW. 题目非常的简单,就是裸的凸包 + 点旋转.这题自己不会的地方就 ...
-
UVA 10652 Board Wrapping(二维凸包)
传送门 刘汝佳<算法竞赛入门经典>P272例题6包装木板 题意:有n块矩形木板,你的任务是用一个面积尽量小的凸多边形把它们抱起来,并计算出木板占整个包装面积的百分比. 输入:t组数据,每组 ...
-
uva 10652 Board Wrapping
主要是凸包的应用: #include <cstdio> #include <cmath> #include <cstring> #include <algor ...
-
●UVA 10652 Board Wrapping
题链: https://vjudge.net/problem/UVA-10652 题解: 计算几何,Andrew求凸包, 裸题...(数组开小了,还整了半天...) 代码: #include<c ...
-
uva 10625 Board Wrapping
https://vjudge.net/problem/UVA-10652 给出n个长方形,用一个面积尽量小的凸多边形把他们围起来 求木板占包装面积的百分比 输入给出长方形的中心坐标,长,宽,以及长方形 ...
随机推荐
-
ES6 - Note4:Class类
1.Class类的介绍 在ES6中新增了Class类的概念,让语法看起来更像是面向对象编程,其实这可以说是一个语法糖,ES5可以做到Class绝大部分功能,但也有一些不同.在ES6以前,可以通过构造函 ...
-
diff详解,读懂diff结果
1.概述 本文将要讨论的是diff命令,diff用来比较两个文件.当然文件比较的工具很多,windows系统下面就有不错的工具可以使用,例如常用的Beyond Compare,WinMerge都是图形 ...
-
渲染voronoi图
渲染voronoi图要比计算voronoi图简单. 渲染voronoi图: 方法1: 在pixel shader里,对每一个像素,求哪个种子点到它的距离最近,将此种子点的颜色作为此像素颜色. 当种子点 ...
-
Linux中printf格式化输出
printf使用文本或者由空格分隔的参数,我们可以在printf中使用格式化字符串.printf不会写像echo那样自动添加换行符,必须手动添加 =========================== ...
-
网络IPC:套接字之套接字选项
套接字机制提供两个套接字选项接口来控制套接字的行为.一个接口用来设置选项,另一个接口允许查询一个选项的状态.可以获取或设置的三种选项: (1)通用选项,工作在所有套接字类型上. (2)在套接字层次管理 ...
-
OpenCV3读取视频或摄像头
我们可以利用OpenCV读取视频文件或者摄像头的数据,将其保存为图像,以用于后期处理.下面的实例代码展示了简单的读取和显示操作: // This is a demo introduces you to ...
-
如何去掉IE控件的垂直滚动条(使用QAxWidget加载IE控件)
如果使用MFC的CHtmlView或Qt的QAxWidget加载IE控件,载入html文件后都会自动带一个垂直滚动条,我们不想要这个滚动条,改怎么办呢?搜索了一下“隐藏IE控件滚动条”,发现在 htt ...
-
MakeFile 文件的作用
makefile文件保存了编译器和连接器的参数选项,还表述了所有源文件之间的关系(源代码文件需要的特定的包含文件,可执行文件要求包含的目标文件模块及库等).创建程序(make程序)首先读取makefi ...
-
device not found解决方案
今天在使用cordova tools进行真机调试的,报了一个错:device not found; 字面意思就是没有发现设备,这时候可以首先尝试重启adb服务 C:\Users\username\Ap ...
-
jQuery 学习(1)——认识jQuery
1.下载 下载地址:http://jquery.com/download/ jquery-3.2.1.js——用于开发和学习(229K) jquery-3.2.1.min.js——用于项目和产品(31 ...