本文主要是介绍占坑抽空补题解_ 【杭电2015年12月校赛B】【计算几何】 Polygon 求直线和多边形的交线长度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
大体做法很好想，就是我们求出这条直线和这个多边形的所有交点。
然后把所有交点按照（x，y）的双关键字排序，然后就能得到所有交线段。
然而，交线段可能在图形内部，也可能在图形外部（比如对于图形'M'，交线恰好连接M的左右上顶点，这条线就会在图形的外部）
所以，再来一步——对于每条交线段，取其中点，判断其是否在凸包内，如果是，那就计入这条线段的长度。
至于具体实现，
我计算几何弱，所以就不写了。
去网上找找模板，就可以AC了。
Polygon
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 215 Accepted Submission(s): 45
Problem Description
Give you a simple polygon and a line, and your task is to calculate the length of the line which is covered by the polygon.
Input
There are several test cases.
Each test case starts with one non-negative integer n (3 <= n <= 1000) giving the number of the vertices of the polygon. Then following n lines, each line contains two real numbers standing for the x and y coordinates of a vertex. The vertices are given either in clockwise or counterclockwise order. Then four real numbers (sx, sy, tx, ty), standing for the coordinates of the two points of the line.
All real numbers are between -100000 and 100000.
Each test case starts with one non-negative integer n (3 <= n <= 1000) giving the number of the vertices of the polygon. Then following n lines, each line contains two real numbers standing for the x and y coordinates of a vertex. The vertices are given either in clockwise or counterclockwise order. Then four real numbers (sx, sy, tx, ty), standing for the coordinates of the two points of the line.
All real numbers are between -100000 and 100000.
Output
For each case print the total length of the line that covered by the polygon, with 3 digits after the decimal point.
Sample Input
4 0 0 0 1 1 1 1 0 0 0 1 1 4 0 0 0 1 1 1 1 0 0 0 1 0 9 0 0 0 2 1 1 2 2 3 1 4 2 5 1 6 2 6 0 0 1 6 1
Sample Output
1.414 1.000 6.000
这篇关于占坑抽空补题解_ 【杭电2015年12月校赛B】【计算几何】 Polygon 求直线和多边形的交线长度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
