計算幾何(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);
		}
	}
}