凸包+半平面交 能过样例求条
查看原帖
凸包+半平面交 能过样例求条
545026
syLph楼主2023/11/14 19:18
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const double eps = 1e-6;
const double PI = acos(-1);

typedef struct{double x,y;}pos;
typedef struct{pos st,ed;}Line;
typedef struct{pos a[4];}Rect;

Rect hh[maxn];
pos pl[maxn],ans[maxn],ap[maxn],KRV[maxn];
int q[maxn],cnt,n,m,s;
Line line[maxn];


bool dcmp(double x,double y){
	if(fabs(x-y)<eps) return 0;
	if(x<y) return -1;
	else return 1;
};

int sign(double x){
	if(fabs(x)<eps) return 0;
	if(x > eps) return 1;
	if(x < -eps) return -1;
}
pos operator -(pos a,pos b){return (pos){a.x-b.x,a.y-b.y};}
pos operator +(pos a,pos b){return (pos){a.x+b.x,a.y+b.y};}
double operator *(pos a,pos b){return a.x*b.y-a.y*b.x;}
double operator &(pos a,pos b){return a.x*b.x+a.y*b.y;}
double area(pos a,pos b,pos c){return (b-a)*(c-a);}
bool cmmp(pos a,pos b){return (a.x == b.x) ? a.y < b.y : a.x < b.x;}
double get_angle(Line a){return atan2(a.ed.y-a.st.y,a.ed.x-a.st.x);}
bool cmp(Line a,Line b){
	double A = get_angle(a),B = get_angle(b);
	if(!dcmp(A,B)) return area(a.st,a.ed,b.ed) < 0;
	return A<B;
}

pos get_line_intersection(pos p,pos v,pos q,pos w){
    pos u = p - q;
    double t = (w * u) / (v * w);
    return {p.x+v.x*t,p.y+v.y*t};
}
pos get_line_intersection(Line a,Line b){
    return get_line_intersection(a.st,a.ed - a.st,b.st,b.ed - b.st);
}
bool on_right(Line& a,Line& b,Line&c){
    pos o = get_line_intersection(b,c);
    return sign(area(a.st,a.ed,o)) <= 0;
}

signed int Andrew(int n){
    int m = 0;sort(KRV,KRV+n,cmmp);
    for(int i = 0 ; i < n ; i ++){
        while((ap[m-1]-ap[m-2])*(KRV[i]-ap[m-2])<=0&&m>1) m--;
        ap[m++] = KRV[i];
    }int k = m;
    for(int i = n - 2 ; i >= 0 ; i --){
        while((ap[m-1]-ap[m-2])*(KRV[i]-ap[m-2])<=0&&m>k) m--;
        ap[m++] = KRV[i];
    } return (n > 1) ? m - 1 : m;
}
double halfplaneintersection(Rect c,int convex_hull_point_num){
	int cnt = 4;
	//for(int i = 0 ; i < cnt ; i ++) printf("%.2lf %.2lf\n",c.a[i].x,c.a[i].y);
	for(int i = 0 ; i < cnt ; i ++) line[i] = {c.a[i],c.a[(i+1)%4]};
	for(int i = 0 ; i < convex_hull_point_num ; i ++)line[cnt++] = (Line){ap[i],ap[(i+1)%convex_hull_point_num]};
	int hh = 0,tt = 0;
	sort(line,line+cnt,cmp);
	for(int i = 0 ; i < cnt ; i ++){
		if(!i&&!dcmp(get_angle(line[i]),get_angle(line[i-1]))) continue;
		while(hh+1<=tt&&on_right(line[i],line[q[tt-1]],line[q[tt]])) tt--;
		while(hh+1<=tt&&on_right(line[i],line[q[hh]],line[q[hh+1]])) hh++;
		q[++tt] = i;
	}
	while(hh+1<=tt&&on_right(line[hh],line[q[tt-1]],line[q[tt]])) tt--;
	while(hh+1<=tt&&on_right(line[tt],line[q[hh]],line[q[hh+1]])) hh++;
	q[++tt] = q[hh];
	int k = 0; double res = 0;
	for(int i = hh ; i < tt ; i ++){
		ans[k++] = get_line_intersection(line[q[i]],line[q[i+1]]); 
	}
	for(int i = 1 ; i < k - 1 ; i ++) res += area(ans[0],ans[i],ans[i+1]) / 2;
	return fabs(res);
}
int getTime(string text)
{
    return stoi(text.substr(0, 2)) * 60 + stoi(text.substr(3));
}
int get_max_cloud(double k){
	double v, m1, m2, m3, m4;
	string time1,time2;
    cin >> v >> time1 >> time2;
    double tot = v * (getTime(time2) - getTime(time1));
	for(int i = 0 ; i < m ; i ++)KRV[m+i] = (pos){KRV[i].x + tot * v / sqrt(k*k+1),KRV[i].y + tot * v / sqrt(k*k+1) * k};
	return Andrew(m * 2);
}

int main(){
	//freopen("testdata.txt","r",stdin);
    int T;
	scanf("%d",&T);
    while(T--){
    	pos ST,ED;
        scanf("%d",&n);
    	for(int i = 0 ; i < n ; i ++) {
            double lx,ly,rx,ry;
            cin >> lx >> ly >> rx >> ry;
            double minx = min(lx, rx), maxx = max(lx, rx);
		    double miny = min(ly, ry), maxy = max(ly, ry);
		    hh[i].a[0] = {minx, miny};
		    hh[i].a[3] = {minx, maxy};
		    hh[i].a[2] = {maxx, maxy};
		    hh[i].a[1] = {maxx, miny};
        }
    	scanf("%d",&m);
    	for(int i = 0 ; i < m ; i ++) scanf("%lf%lf",&KRV[i].x,&KRV[i].y);
    	scanf("%lf%lf%lf%lf",&ST.x,&ST.y,&ED.x,&ED.y);
    	double k = (ST.y-ED.y) / (ST.x-ED.x+eps);
    	bool ol = true;
    	int cov = get_max_cloud(k);
        //for(int i = 0 ; i < cov ; i ++) printf("%.2lf %.2lf\n",ap[i].x,ap[i].y);
		double ans = 0;
		for(int i = 0 ; i < n ; i ++) ans += halfplaneintersection(hh[i],cov);
		printf("%.1lf\n",ans);
	}
	return 0;
}
2023/11/14 19:18
加载中...