acm几何学算法基础

acm几何学算法基础

ID:24849315

大小:245.00 KB

页数:51页

时间:2018-11-16

acm几何学算法基础_第1页
acm几何学算法基础_第2页
acm几何学算法基础_第3页
acm几何学算法基础_第4页
acm几何学算法基础_第5页
资源描述:

《acm几何学算法基础》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、西南交通大学计算机与通信工程学院2005年1月程序设计基础算法IntersectingLinesWeallknowthatapairofdistinctpointsonaplanedefinesalineandthatapairoflinesonaplanewillintersectinoneofthreeways:1)nointersectionbecausetheyareparallel,2)intersectinalinebecausetheyareontopofoneanother(i.e.theyarethesameline),3)intersectinapoi

2、nt.Inthisproblemyouwilluseyouralgebraicknowledgetocreateaprogramthatdetermineshowandwheretwolinesintersect.Yourprogramwillrepeatedlyreadinfourpointsthatdefinetwolinesinthex-yplaneanddeterminehowandwherethelinesintersect.Allnumbersrequiredbythisproblemwillbereasonable,saybetween-1000and100

3、0.InputThefirstlinecontainsanintegerNbetween1and10describinghowmanypairsoflinesarerepresented.ThenextNlineswilleachcontaineightintegers.Theseintegersrepresentthecoordinatesoffourpointsontheplaneintheorderx1y1x2y2x3y3x4y4.Thuseachoftheseinputlinesrepresentstwolinesontheplane:thelinethrough

4、(x1,y1)and(x2,y2)andthelinethrough(x3,y3)and(x4,y4).Thepoint(x1,y1)isalwaysdistinctfrom(x2,y2).Likewisewith(x3,y3)and(x4,y4).OutputThereshouldbeN+2linesofoutput.ThefirstlineofoutputshouldreadINTERSECTINGLINESOUTPUT.Therewillthenbeonelineofoutputforeachpairofplanarlinesrepresentedbyalineof

5、input,describinghowthelinesintersect:none,line,orpoint.Iftheintersectionisapointthenyourprogramshouldoutputthexandycoordinatesofthepoint,correcttotwodecimalplaces.Thefinallineofoutputshouldread``ENDOFOUTPUT".SampleInput5 00440440 50761023 50763-64-3 2022715185 03401225SampleOutputINTERSEC

6、TINGLINESOUTPUT POINT2.002.00 NONE LINE POINT2.005.00 POINT1.072.20 ENDOFOUTPUT计算几何学算法设计1、确定任意两条线段是否都不相交设有一组线段,要求判断这组线段中任意两条线段是否都不相交。问题分析:对于一组线段,我们可以先假设这组线段中不存在与垂直轴平行的线段,同时也没有三条线段相交于一点的情况。基于这种假设,我们可以通过一根垂直扫描线来扫描这组线段,在扫描过程中我们可以发现,一旦两条线段存在交点,则其扫描的结果会发生变化。即垂直扫描线自上而下扫描时的输出会发生变化,如下图所示。ABCDABAB

7、ACDABCADCBDCBCDC从上面的图可以看出,如果两条线段之间存在交点,则在交点前后两点之间的顺序将发生变化。因此我们可以通过如下算法来判断哪些线段之间存在交点:1、将所有线段的端点按照X坐标从小到大的顺序进行排列,如果两个端点的X坐标相同,则将Y坐标小的放在前面,Y坐标大的放在后面。设该集合为S。2、取S集合中的一个端点p。如果p是线段s的左端点,则将其插入序列T中;否则将其从序列中删除。插入的方法是:若p在T集合中某线段的上方则插入到该线段的前面,否则查找下一条线段。这儿如何判断在p点在T集合某线段的上方呢?我们看一

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。