题目：给你一个平面的多边形，再给你一条平行于y轴的直线，问直线被多边形截取的总长是否超过目标。
分析：计算几何。
方法一：1.求出所有直线和多边形交点。（O（N））
2.对交点按纵坐标排序，则排序后这些点一定相邻。（O（NlgN））
3.判断每对相邻点间的线段和多边形的关关{内|外}，在内的增加截取长度。（O（N*N））
因为，数据规模到达10000，判断线段和多边形关系是O（N）所以会TLE。
方法二：在计算过程中判断当前线段与多边形关系，需要O（1）的算法。见图P2
利用一个变量flag记录直线当前部分和多边形位置关系，那么：
1.直线和多边形交点不是顶点，那么直线穿过相交条边后会改变和多边形关系。
2.直线和多边形的边共线，不改变直线状态（将这条边看成是一个点），不改变截取长度。
3.直线经过多边形顶点（不共线），同一顶点属于两条直线，只计算第一次经过。
这里需要注意，我们利用当前交点所在两边的端点，判断他们与直线X的关系：
a.两端点在直线同侧，则不改变直线在多边形的内外关系。
b.两端点在直线两侧，则直线和多边形的关系会改变。
在计算过程中，如果flag标记在直线内，就把这段加入截取的总长度即可。
P1 P2
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#define eps 1e-3
using namespace std;
typedef struct pnode
{
double x,y;
pnode( double a, double b ) {x = a;y = b;}
pnode(){};
}point;
point P[20001];
point E[4];
point C[10001];
typedef struct lnode
{
double x,y,dx,dy;
lnode( point a, point b ) {x = a.x;y = a.y;dx = b.x-a.x;dy = b.y-a.y;}
lnode(){};
}line;
//两点间距离
double dist( point a, point b )
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
//线段相交
bool s_cross_s( line a, line b )
{
double t1 = 0.0+a.dx*(b.y-a.y)-a.dy*(b.x-a.x);
double t2 = 0.0+a.dx*(b.y+b.dy-a.y)-a.dy*(b.x+b.dx-a.x);
double t3 = 0.0+b.dx*(a.y-b.y)-b.dy*(a.x-b.x);
double t4 = 0.0+b.dx*(a.y+a.dy-b.y)-b.dy*(a.x+a.dx-b.x);
return (t1*t2 <= 0)&&(t3*t4 <= 0);
}
//两直线交点
point crosspoint( line l, double x )
{
if ( fabs( l.dx ) < eps )
return point( x, l.y );
return point( x, l.y+l.dy/l.dx*(x-l.x) );
}
//计算空的最大长度
int judge( int N, int L, int X )
{
int top = 0;
for ( int i = 0 ; i < 4 ; ++ i )
E[i] = P[0];
for ( int i = 0 ; i < N ; ++ i ) {
if ( P[i].x > E[3].x ) E[3].x = P[i].x+1;
if ( P[i].y > E[3].y ) E[3].y = P[i].y+1;
if ( P[i].x < E[0].x ) E[0].x = P[i].x-1;
if ( P[i].y < E[0].y ) {
E[0].y = P[i].y-1;
top = i;//记录顶点
}
}
for ( int i = 0 ; i < N ; ++ i )
P[i+N] = P[i];
point p1 = point( X, E[0].y );
point p2 = point( X, E[3].y );
line m = line ( p1, p2 );
double sum = 0.0;
int flag = 0,count = 0;
C[count ++] = p1;p2 = P[top+N-1];
for ( int i = top ; i < top+N ; ++ i ) {
line l = line( P[i], P[i+1] );
if ( s_cross_s( m, l ) ) {
point New = crosspoint( l, X );
if ( dist( New, P[i] ) > eps && P[i].x != P[i+1].x ) p2 = P[i];
//如果交点是多边形的顶点，只计算第一次相交
if ( dist( New, P[i+1] ) < eps ) continue;
C[count ++] = New;
if ( P[i].x != P[i+1].x ) {
if ( flag ) sum += dist( C[count-1], C[count-2] );
if ( s_cross_s( m, line( p2, P[i+1] ) ) ) flag = !flag;
}
}
}
return (sum > L);
}
int main()
{
int T,N,L,X;
while ( scanf("%d",&T) != EOF )
while ( T -- ) {
scanf("%d",&N);
for ( int i = 0 ; i < N ; ++ i )
scanf("%lf%lf",&P[i].x,&P[i].y);
scanf("%d%d",&L,&X);
if ( judge( N, L, X ) ) printf("YES\n");
else printf("NO\n");
}
return 0;
}P2已经给出所有可能可以根据P2自造数据，测试数据（P2）：5 8 4 1 3 2 4 4 3 4 2 5 2 3 0 1 2 0 2 3 9 4 1 3 2 4 4 3 4 2 5 3 6 2 7 0 1 2 0 2 3 12 4 1 3 1 4 2 3 2 3 3 4 4 2 4 3 5 3 6 2 7 0 1 2 0 2 3 11 4 1 3 1 4 2 3 2 3 3 2 4 3 5 3 6 2 7 0 1 2 0 2 3
UVa 858 - Berry Picking,布布扣,bubuko.com
原文：http://blog.csdn.net/mobius_strip/article/details/22182407