poj2318 TOYS 线划分矩形
题目链接：http://poj.org/problem?id=2318
//题目意思：
//在一个矩形中用n条线来划分（划分的线不交叉此而且只能分左右方向 ），//代码如下：
#include<iostream>#include<cstdio>#include<math.h>#define eps 1e-8struct Point{double x,y;};struct Line{double a,b,c;};int _sign(double x){return x>eps? 1:(x<-eps)? 2 : 0;}double xmult(Point p1,Point p2,Point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}Line twoPoLine(Point p1,Point p2){Line l;l.a=p2.y-p1.y;l.b=p1.x-p2.x;l.c=p2.x*p1.y-p1.x*p2.y;return l;}bool isRight(Point q,Line l){return l.a*q.x+l.b*q.y+l.c>0.0;}Line l[5002];Point Q[5002];Point p[5002][2];int flag[5002];int main(){double x1,y1,x2,y2;int n,m,k=0;while(scanf("%d",&n),n){scanf("%d",&m);scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);int i,j;for(i=0;i<n;i++){Point p1,p2;scanf("%lf%lf",&p[i][0].x,&p[i][1].x);p[i][0].y=y1;p[i][1].y=y2;}for(i=0;i<m;i++){scanf("%lf%lf",&Q[i].x,&Q[i].y);flag[i]=true;}int sum=0;if(k>0)printf("\n");for(i=0;i<n;i++){int cnt=0;for(j=0;j<m;j++)if(flag[j]){if(xmult(p[i][0],Q[j],p[i][1])>eps){cnt++;flag[j]=false;}}sum+=cnt;printf("%d: %d\n",i,cnt);}printf("%d: %d\n",i,m-sum);k++;}return 0;}