acm几何学算法基础

《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".SampleInput5004404405076102350763-64-3202271518503401225SampleOutputINTERSEC

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

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