开发工具:
文件大小: 10mb
下载次数: 0
上传时间: 2009-05-23
详细说明： POJ部分解题代码 解题报告：Fence 题目来源：POJ 1031 解法或类型： 计算几何 作者：杨清玄 Fence Time Limit:1S Memory Limit:1000K Total Submit:103 Accepted:26 Description There is an area bounded by a fence on some flat field. The fence has the height h and in the plane projection it has a form of a closed polygonal line (without self-intersections), which is specified by Cartesian coordinates (Xi, Yi) of its N vertices. At the point with coordinates (0, 0) a lamp stands on the field. The lamp may be located either outside or inside the fence, but not on its side as it is shown in the following sample pictures (parts shown in a thin line are not illuminated by the lamp): The fence is perfectly black, i.e. it is neither reflecting, nor diffusing, nor letting the light through. Research and experiments showed that the following law expresses the intensity of light falling on an arbitrary illuminated point of this fence: I0=k/r where k is a known constant value not depending on the point in question, r is the distance between this point and the lamp in the plane projection. The illumination of an infinitesimal narrow vertical board with the width dl and the height h is dI=I0*|cosα|*dl*h where I0 is the intensity of light on that board of the fence, α is the angle in the plane projection between the normal to the side of the fence at this point and the direction to the lamp. You are to write a program that will find the total illumination of the fence that is defined as the sum of illuminations of all its illuminated boards. Input The first line of the input file contains the numbers k, h and N, separated by spaces. k and h are real constants. N (3 <= N <= 100) is the number of vertices of the fence. Then N lines follow, every line contains two real numbers Xi and Yi, separated by a space. Output Write to the output file the total illumination of the fence rounded to the second digit after the decimal point. Sample Input 0.5 1.7 3 1.0 3.0 2.0 -1.0 -4.0 -1.0 Sample Output 5.34 Source Northeastern Europe 1998 解题思路： 本题是一道计算几何的题目。首先，由于题目可以得到dI=I0*|cosα|*dl*h 也就是说一条边的总照度为 = = =a*h*k 其中下，X1，X2为一条边的坐右端点，a为这条边对原点所张的角度 所以实际上本题是要求整个FENCE区域对原点所张开的总角度， 定义FENCE为一有向回路 那么每条边都是有向的。。如果按照边的方向对原点所张开的角度为顺时针。那么定义为正。逆时针为负。并且每输入一条边就把本边对原点张开的角度计算进去加到一个数里去 那么对于包含原点的区域。这个数应该为正负2 ； 对于不包含原点的区域，这个数在按边过程中的最大值-最小值就是这个区域对原点所张开的角度。 还有一种情况，那就是区域不包含原点，但是总共张开的角度大于2 ，那么只要计算为2 即可因为原点对任何区域最多只能张开2 。 数据结构： 用一个POINT数组来储存点的位置 时空分析： 如果有N个点 那么空间复杂度为O（N） 时间复杂度为O（N） 源程序： fence.cpp ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
