C20220801T2 marisa

标签：ll bj 随机化 long C20220801T2 marisa

考场上写挂这一道题，白给。（数组开小+随机化次数太少）

没想到评测机这么给力 ，直接随机化 \(2\times 10^5\) 个点，只要有一个在所有带状区域之外就没有覆盖，否则可以视为覆盖，这里怕有奇怪的数据，特判了一下四个角落，然后就跑的飞快了。

正解：PDF没看懂，讲题人没到场，end

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll in(){
    ll x=0,f=1;
    char c;
    do{
        c=getchar();
        if(c=='-')
        	f=-1;
    }while(c>'9' || c<'0');
    while(c<='9' && c>='0'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}

double rnd(){
	return (double)rand()/(double)RAND_MAX;
}



double X,Y;
double A[2005],B[2005],C[2005],D[2005];
int flag,n,t;
int main(){
	freopen("marisa.in","r",stdin);
    freopen("marisa.out","w",stdout);
	srand(time(0));
	t=in();
	while(t--){
		X=in(),Y=in(),n=in();
		for(int i=1;i<=n;++i){
			A[i]=in(),B[i]=in(),C[i]=in(),D[i]=in();
		}
		flag=0;
		for(int i=1;i<=200000;++i){
			double x=rnd()*X;
			double y=rnd()*Y;
			if(i==1){
				x=0,y=0;
			}
			if(i==2){
				x=0,y=Y;
			}
			if(i==3){
				x=X,y=0;
			}
			if(i==4){
				x=X,y=Y;
			}
			int bj=0;
			for(int j=1;j<=n;++j){
				if(C[j]<=A[j]*x+B[j]*y && D[j]>=A[j]*x+B[j]*y){
					bj=1;
					break;
				}
			}
			if(bj==0){
				flag=1;
				break;
			}
		}
		printf("%d",flag);
	}
	return 0;
}

标签：ll,bj,随机化,long,C20220801T2,marisa
From： https://www.cnblogs.com/zhouzizhe/p/16642686.html