点击打开hdu2528
这个题目看完题目后就应该知道是要求渠道与校区的交点，也就是求一条直线与多边形的交点,题目有一个重要的信息的——渠道一定会通过校园，那么题目就不用考虑特殊情况，
直接求直线与多边形交点就可以过。
求的时候，先要判断线段与直线是否相交，再求交点，这里的线段就是多边形的每条边。判断的话可以利用直线与线段求交点的模板。我这里是利用直线的方向向量，就是题目给出的两个点，这里记作向量ab,先用向量ab与多边形的每一对相邻的点求叉乘，因为相邻的两个点求出的叉乘相乘为负数，那么肯定该线段与直线相交，在求交点。
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<algorithm>using namespace std;const double eps=1e-8;const int maxn = 505;struct point{double x,y;};struct ploy{point node[ maxn ];int n;};point left,right,s;ploy p,p1,p2;double cross( point a,point b,point c ){ ///叉乘return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}double ploy_area( ploy res ){///求多边形面积double ans=0;res.node[ res.n ]=res.node[0];for( int i=0;i<res.n;i++ ){ans+=cross( s,res.node[i],res.node[i+1] );}return ans;}int dblcmp(double a) {return a<-eps?-1:a>eps?1:0;}///精度判断ploy cut( ploy p,point s,point e ){point tmp;ploy bb;int cnt=0;for( int i=0;i<p.n;i++ ){int d1,d2;double s1,s2;d1=dblcmp(s1=cross( p.node[i],s,e ));//跨立d2=dblcmp(s2=cross( p.node[i+1],s,e ));//跨立if( d1>=0 ){bb.node[ cnt ]=p.node[ i ];cnt++;}if( d1*d2<0 ){tmp.x=(s2*p.node[i].x-s1*p.node[i+1].x)/(s2-s1);tmp.y=(s2*p.node[i].y-s1*p.node[i+1].y)/(s2-s1);bb.node[ cnt ]=tmp;cnt++;}}bb.n=cnt;bb.node[ cnt ]=bb.node[ 0 ];return bb;}int main(){while( scanf("%d",&p.n),p.n ){for( int i=0;i<p.n;i++ ){scanf("%lf%lf",&p.node[ i ].x,&p.node[ i ].y);}p.node[ p.n ]=p.node[ 0 ];scanf("%lf%lf%lf%lf",&left.x,&left.y,&right.x,&right.y);s.x=s.y=0;p1=cut( p,left,right );p2=cut( p,right,left );int res1,res2;res1=int(fabs(ploy_area( p1 ))/2+0.5);res2=int(fabs(ploy_area( p2 ))/2+0.5);printf("%d %d\n",res1>res2?res1:res2,res1>res2?res2:res1);}return 0;}