计算几何(3)

1.https://codeforces.com/problemset/problem/793/C 2300的计算几何真恶心啊

题意:n条射线,问全部到达一个矩形"内部"的时间

思路:1.如果p1在内部,那就只有一个时间点,如果在外部,射入会有一个或两个时间点.

2.获得一段时间段后,取交集.

注意:如果点在边缘,而且射线方向平行与x,y轴,那只会从矩形边缘擦过,输出-1

还有一个,我是先判断一条直线和边框直线有没有交点,然后判断交点在射线上,再判断交点在线段上.挺麻烦.

交点在射线上用向量判断同方向,

const int N = 1e5 + 50;
const int INF = 0x7fffffff;
const double eps = 1e-9;
const double PI = acos(-1);

int sgn(double x) {
	if(fabs(x) < eps)return 0;
	else return x<0?-1:1;
}

struct Point {
	double x,y;
	Point() {}
	Point(double x,double y):x(x),y(y) {}
	Point operator + (Point B) {
		return Point(x+B.x,y+B.y);
	}
	Point operator - (Point B) {
		return Point(x-B.x,y-B.y);
	}
	Point operator /(double k) {
		return Point(x/k,y/k);
	}
	bool operator == (Point B) {
		return x == B.x && y == B.y;
	}
};

struct Line {
	Point p1,p2;//线上的两个点
	Line() {}
	Line(Point p1,Point p2):p1(p1),p2(p2) {}

};


double Distance(Point A,Point B) {
	return hypot(A.x-B.x,A.y-B.y);
//	return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}

double Cross(Point a,Point b) {
	return a.x*b.y-a.y*b.x;
}

typedef  Point Vector;

double Dot(Vector A,Vector B) {
	return A.x*B.x + A.y*B.y;   //点积
}


//点和直线关系:1 在左侧;2 在右侧;0 在直线上
int Point_line_relation(Point p,Line v) {
	int c = sgn(Cross(p-v.p1,v.p2-v.p1));
	if(c < 0)return 1; //1：p在v的左边
	if(c > 0)return 2; //2：p在v的右边
	return 0; //0：p在v上
}


//两直线关系:0 平行,1 重合,2 相交
int Line_relation(Line v1, Line v2) {
	if(sgn(Cross(v1.p2-v1.p1,v2.p2-v2.p1)) == 0) {
		if(Point_line_relation(v1.p1,v2)==0) return 1;//1 重合
		else return 0;//0 平行
	}
	return 2; //2 相交
}


//求两直线ab和cd的交点
//调用前要保证两直线不平行或重合
Point Cross_point(Point a,Point b,Point c,Point d) { //Line1:ab, Line2:cd
	double s1 = Cross(b-a,c-a);
	double s2 = Cross(b-a,d-a); //叉积有正负
	return Point(c.x*s2-d.x*s1,c.y*s2-d.y*s1)/(s2-s1);
}


// 点和线段的关系：0 点p不在线段v上；1 点p在线段v上。
bool Point_on_seg(Point p, Line v) {
	return sgn(Cross(p-v.p1, v.p2-v.p1)) == 0 && sgn(Dot(p - v.p1,p- v.p2)) <=0;
}

bool Point_on_sx(Point a,Line p) {
	if((a.x-p.p1.x)*(p.p2.x-p.p1.x) < 0)return false;
	if((a.y-p.p1.y)*(p.p2.y-p.p1.y) < 0)return false;
	return true;
}



int n;
Point A,B,p[N];
Line l[5];
Line x[N];
double dis[N][2];
int tot=0;

void work() {
	scanf("%d",&n);
	scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);
	l[0] = Line(Point(A.x,A.y),Point(B.x,A.y));
	l[1] = Line(Point(B.x,A.y),Point(B.x,B.y));
	l[2] = Line(Point(B.x,B.y),Point(A.x,B.y));
	l[3] = Line(Point(A.x,B.y),Point(A.x,A.y));
	for(int i=0; i<n; i++) {
		double nx,ny;
		scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&nx,&ny);
		x[i] = Line(p[i],p[i]+Point(nx,ny));
	}

	int f=1;

	for(int i=0; i<n; i++) {
		//判断从边缘擦过的情况
		if(p[i].x == A.x || p[i].x == B.x || p[i].y == A.y || p[i].y == B.y) {
			if(sgn(x[i].p2.x-x[i].p1.x) == 0 || sgn(x[i].p2.y-x[i].p1.y) == 0) {
				f=0;
				break;
			}
		}
		tot=0;
		//记录两个时间点
		for(int j=0; j<4; j++) {
			if(Line_relation(x[i],l[j]) == 2 ) {
				Point z = Cross_point(x[i].p1,x[i].p2,l[j].p1,l[j].p2);
				if(Point_on_sx(z,x[i]) && Point_on_seg(z,l[j])) {  //点在射线上
					double dd = Distance(p[i],z);
					//可能存在经过三条边(经过一个顶点)甚至两个顶点...要特判
					if(tot == 0 || (tot == 1 && fabs(dis[i][0] - dd) > eps) ||
					        (tot == 2 && fabs(dis[i][0] - dd) > eps && fabs(dis[i][1]-dd)>eps))
						dis[i][tot++] = dd;
				}
			}
		}
		int ok = 0;
		//如果在内部,特殊处理
		if(p[i].x >= A.x && p[i].x <= B.x && p[i].y >= A.y && p[i].y <= B.y) {
			if(tot != 2) {
				tot = 2;
				ok = 1;
				dis[i][1] = dis[i][0];
				dis[i][0] = 0.0;
			}
		}

		//不在内部而且有两个交点在同一点 -> 经过一个矩形顶点
		if(tot != 2 || (!ok && fabs(dis[i][0] - dis[i][1]) < eps)) {
			f = 0;
			break;
		}
		if(dis[i][0] > dis[i][1])swap(dis[i][0],dis[i][1]);
	}

	if(f == 0)printf("-1
");
	else {
		double l=0,r=100000000;
		for(int i=0; i<n; i++) {
			l = max(l,dis[i][0]/Distance(x[i].p1,x[i].p2));
			r = min(r,dis[i][1]/Distance(x[i].p1,x[i].p2));
		}
		if(l >= r ) printf("-1
");
		else {
			printf("%.8f
",l);
		}
	}
}