程序员人生 网站导航

UVA 10652 Board Wrapping 计算几何

栏目:互联网时间:2014-11-08 08:16:40


多边形凸包。。。。


Board Wrapping
Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu

Submit Status

Description

Download as PDF

Problem B

Board Wrapping

Input: standard input
Output: standard output

Time Limit: 2 seconds


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 n1< 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, j where 0 <= x, y, w, h <=10000 and 

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐

1.cyou 非常适合 Z 世代企业家的三大理由 2阿里、京东类ChatGPT产品正在内测 未来或将融入产品 3公会积极复工复产,2023直播行业有哪些新机遇? 4三维天地亮相全球工业互联网大会 分享AI赋能数据治理前沿实践 5公众号买500个粉丝对账号有影响吗(实话分享) 6AI驱动标准化新时代:三维天地亮相东盟论坛,分享检验检测行业智慧变革 7 bilibili粉丝1000可以买吗(个人揭秘)