• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

凸包与直线的关系

开发技术 开发技术 5小时前 4次浏览

给一个逆时针的凸包和一条线,问你线的左边的和凸包的交面积
https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/4/CGL_4_C

int n;
Point p[N],ch[N];
Point last[N];  //最后存在的点
//两直线交点
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);
}

double area(int n,Point a[]) {  //求面积[0,n]
	double res=0;
	n++;
	for(int i=0; i<n; i++) {
		res+=(a[i]-a[0])^(a[(i+1)%n]-a[0]);
	}
	return res/2.0;
}

double convex_cut(Point p1,Point p2) { //p1->p2,右边不要
	int al=-1;
	for(int i=0; i<n; i++) {
		int t1=sgn((p2-p1)^(p[i]-p1));
		int t2=sgn((p2-p1)^(p[(i+1)%n]-p1));
		if(t1 >=0)last[++al]=p[i];    //p1在线左边(逆时针方向)
		if(t1*t2<0)last[++al]=Cross_point(p[i],p[(i+1)%n],p1,p2);  //直线穿过,取交点
	}
	double res=area(al,last);
	return res;
}

void work() {
	scanf("%d",&n);
	for(int i=0; i<n; i++) {//逆时针给出的凸包
		scanf("%lf%lf",&p[i].x,&p[i].y);
	}
	int q;scanf("%d",&q);
	while(q--) {
		Point p1,p2;
		scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y);
		double ans = convex_cut(p1,p2);
		printf("%.8fn",ans);
	}
}

程序员灯塔
转载请注明原文链接:凸包与直线的关系
喜欢 (0)