#include #include #include typedef struct {double x, y;} point; typedef struct {point p1,p2;} line; int intersect(point *p,line l1, line l2) { double A,B,C,D,E,F; A = l1.p1.x * l1.p2.y - l1.p1.y * l1.p2.x; B = l2.p1.x * l2.p2.y - l2.p1.y * l2.p2.x; C = l1.p1.x - l1.p2.x; D = l2.p1.x - l2.p2.x; E = l1.p1.y - l1.p2.y; F = l2.p1.y - l2.p2.y; p->x = (A*D - C*B) / (C*F - E*D); p->y = (A*F - E*B) / (C*F - D*E); if(isnan(p->x) || isinf(p->x) || isnan(p->y) || isinf(p->y)) return 0; return 1; } void printpoint(point *p) { printf("(%lf,%lf)",p->x,p->y); } void printline(line *l) { printf("["); printpoint(&(l->p1)); printf(","); printpoint(&(l->p2)); printf("]"); } int liesbetween(point p, line l) { double dxc,dyc,dxl,dyl,cross; dxc = p.x - l.p1.x; dyc = p.y - l.p1.y; dxl = l.p2.x - l.p1.x; dyl = l.p2.y - l.p1.y; // we know p is on the line, just check endpoints /* cross = dxc * dyl - dyc * dxl; */ /* if (cross != 0) */ /* return 0; */ if (fabs(dxl) >= fabs(dyl)) return dxl > 0 ? l.p1.x<=p.x && p.x<=l.p2.x : l.p2.x<=p.x && p.x<=l.p1.x; else return dyl > 0 ? l.p1.y<=p.y && p.y<=l.p2.y : l.p2.y<=p.y && p.y<=l.p1.y; } int lieson(point p, line l) { double dxc,dyc,dxl,dyl,cross; dxc = p.x - l.p1.x; dyc = p.y - l.p1.y; dxl = l.p2.x - l.p1.x; dyl = l.p2.y - l.p1.y; cross = dxc * dyl - dyc * dxl; if (fabs(cross) < 0.0000001) return 1; return 0; } int colinear(line l1,line l2) { if(lieson(l1.p1,l2)&&lieson(l1.p2,l2)) return 1; return 0; } int samepoint(point a, point b) { if(a.x == b.x && a.y==b.y) return 1; return 0; } int main() { line *streets; line properties; point ip; int i,j,Nstr,Ntst,count; int fline=1; double t1,t2,t3,t4; if(scanf("%d",&Nstr)!=1) { fprintf(stderr,"File ended early at line %d\n",fline); exit(1); } fline++; streets = malloc(sizeof(line)*Nstr); for(i=0;i