poj 1066 线段相交

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <math.h>

#define MAXX 35
#define eps 1e-6
using namespace std;

typedef struct point
{
    double x,y;
} point;
typedef struct line
{
    point st,ed;
} line;

bool dy(double x,double y)
{
    return x>y+eps;
}
bool xy(double x,double y)
{
    return x<y-eps;
}
bool xyd(double x,double y)
{
    return x<y+eps;
}
bool dyd(double x,double y)
{
    return x>y-eps;
}
bool dd(double x,double y)
{
    return fabs(x-y)<eps;
}

double crossProduct(point a,point b,point c)
{
    return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
}

bool onSegment(point a,point b,point  c)
{
    double maxx=max(a.x,b.x);
    double maxy=max(a.y,b.y);
    double minx=min(a.x,b.x);
    double miny=min(a.y,b.y);
    if(dd(crossProduct(a,b,c),0.0)&&xyd(c.x,maxx)&&dyd(c.x,minx)
            &&xyd(c.y,maxy)&&dyd(c.y,miny))
        return true;
    return false;
}

bool segIntersect(point p1,point p2,point p3,point p4)
{
    double d1=crossProduct(p3,p4,p1);
    double d2=crossProduct(p3,p4,p2);
    double d3=crossProduct(p1,p2,p3);
    double d4=crossProduct(p1,p2,p4);
    if(xy(d1*d2,0.0)&&xy(d3*d4,0.0))
        return true;
    /*if(dd(d1,0.0)&&onSegment(p3,p4,p1))
        return true;
    if(dd(d2,0.0)&&onSegment(p3,p4,p2))
        return true;
    if(dd(d3,0.0)&&onSegment(p1,p2,p3))
        return true;
    if(dd(d4,0.0)&&onSegment(p1,p2,p4))
        return  true;
        */
    return false;
}

point p[10010];
line li[MAXX];
int num[MAXX];

int main()
{
    int n,m,i,j;
    point tar;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0; i<n; i++)
        {
            scanf("%lf%lf%lf%lf",&li[i].st.x,&li[i].st.y,&li[i].ed.x,&li[i].ed.y);
        }
        scanf("%lf%lf",&tar.x,&tar.y);
        i=0;
        int cas=0;
        for(j=1; j<100; j++)
        {
            p[cas].x=0;
            p[cas++].y=j;
        }
        for(j=1; j<100; j++)
        {
            p[cas].x=100;
            p[cas++].y=j;
        }
        for(i=1; i<100; i++)
        {
            p[cas].x=i;
            p[cas++].y=0;
        }
        for(i=1; i<100; i++)
        {
            p[cas].x=i;
            p[cas++].y=100;
        }
        int sum;
        int minn=0x7fffffff;//printf("%d**\n",cas);
        for(i=0; i<cas; i++)
        {
            sum=0;
            for(j=0; j<n; j++)
            {
                if(segIntersect(tar,p[i],li[j].st,li[j].ed))
                {
                    sum++;
                }
            }
            if(minn>sum)
            {
                minn=sum;
            }//printf("%d**\n",sum);
        }
        if(n == 0) printf("Number of doors = 1\n");
        else
            printf("Number of doors = %d\n",minn+1);
    }

    return 0;
}