QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#35051#851. (Almost) Fair Cake-CuttingFroggyguaAC ✓3ms3892kbC++176.6kb2022-06-12 22:05:432022-06-12 22:05:46

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-12 22:05:46]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 3892kb
  • [2022-06-12 22:05:43]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-9;
const double PI=acos(-1.0);
const double inf=1e9+233;
//Vector可以用Point来表示 
struct Point{
	double x,y;
	Point(double _x=0,double _y=0):x(_x),y(_y){}
	//相等
	friend bool operator ==(const Point &a,const Point &b){
		return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
	}
	//不相等 
	friend bool operator !=(const Point &a,const Point &b){
		return !(a==b);
	}
	//相加 
	friend Point operator + (const Point &a,const Point &b){
		return Point(a.x+b.x,a.y+b.y);
	}
	//相减 
	friend Point operator - (const Point &a,const Point &b){
		return Point(a.x-b.x,a.y-b.y);
	}
	//点积 
	friend double operator * (const Point &a,const Point &b){
		return a.x*b.x+a.y*b.y;
	}
	//叉积 
	friend double operator % (const Point &a,const Point &b){
		return a.x*b.y-a.y*b.x;
	}
	//长度 
	inline double len(){
		return sqrt(x*x+y*y);
	}
	//单位向量
	Point unit(){
		double l=len();
		return Point(x/l,y/l);
	} 
	//求单位法向量 
	inline Point normal(){
		double l=len();
		return Point(-y/l,x/l);
	}
	//点从下往上排序
	inline bool operator < (Point b){
		return fabs(y-b.y)<eps?x<b.x:y<b.y; 
	} 
	//平面直角坐标系上半部分优先
	inline bool Quad(){
		return y>eps||(fabs(y)<=eps&&x>=-eps);
	} 
};
inline Point operator * (double k,Point a){
	return Point(a.x*k,a.y*k);
}
//两个向量的夹角 
inline double Angle(Point a,Point b){
	//return acos(a*b/a.len()/b.len());
	double tmp=atan2(b.y,b.x)-atan2(a.y,a.x); 
	while(tmp>=PI+eps)tmp-=2*PI;
	while(tmp<=-PI-eps)tmp+=2*PI;
	return tmp;
}
//判断两个向量是否平行
inline bool Para(Point a,Point b){
	return fabs(a%b)<=eps;
} 
//判断向量a是否在向量b的左侧
inline bool Left(Point a,Point b){
	return b%a>eps;
} 
//逆时针旋转p后的向量 
inline Point Rotate(Point a,double p){
	return Point(a.x*cos(p)-a.y*sin(p),a.x*sin(p)+a.y*cos(p));
}
//绕LTL逆时针排序 

//直线 
struct Line{
	Point p[2];
	Line(Point a=Point(0,0),Point b=Point(0,0)){p[0]=a,p[1]=b;}
	inline Point& operator [] (int i){
		return p[i];
	}
	inline Point v(){
		return p[1]-p[0];
	}
};
//直线交点 
inline Point Cross(Line a,Line b){
	return a[0]+((b[0]-a[0])%(b[1]-a[0]))/((a[1]-a[0])%(b[1]-b[0]))*(a[1]-a[0]);
} 
//多边形 
typedef vector<Point> Poly;
//面积 
double Area(Poly A){
	if(A.empty())return 0.0;
	double tot=0;
	for(int i=0;i<(int)A.size()-1;++i){
		tot+=A[i]%A[i+1];
	}
	tot+=A[(int)A.size()-1]%A[0];
	return fabs(tot)/2.0;
} 
//周长
double C(Poly A){
	double tot=0;
	for(int i=0;i<(int)A.size()-1;++i){
		tot+=(A[i+1]-A[i]).len();
	}
	tot+=(A[A.size()-1]-A[0]).len();
	return tot;
} 
//重心 
Point Cent(Poly A){
	double x=0,y=0,m=0;
	for(int i=1;i<(int)A.size()-1;++i){
		double tmp=(A[i]-A[0])%(A[i+1]-A[0]);
		x+=tmp*(A[0].x+A[i].x+A[i+1].x)/3.0;
		y+=tmp*(A[0].y+A[i].y+A[i+1].y)/3.0;
		m+=tmp;
	}
	return Point(x/m,y/m);
} 
//求凸包
Poly Convex(Poly A){
	Point LTL=(*min_element(A.begin(),A.end())); //Lower Then Left
	sort(A.begin(),A.end(),[&](Point a,Point b){
		a=a-LTL,b=b-LTL;
		return Para(a,b)?a.len()<b.len():Left(b,a);
	});
	Poly st;
	for(auto p:A){
		while(st.size()>1&&!Left(p-st[(int)st.size()-2],st.back()-st[(int)st.size()-2]))st.pop_back();
		st.push_back(p);
	}
	return st;
}
// 求点是否在多边形内(单次询问,可以是凹多边形)
inline bool Inside_1(Poly A,Point p){
	double tot=0;
	for(int i=0;i<(int)A.size();++i)tot+=Angle(A[i]-p,A[(i+1)%A.size()]-p);
	return fabs(tot)>=eps;
} 
//多组询问
inline bool Inside_2(Poly &A,Point p){
	if(p==A[0])return true;
	if(Left(p-A[0],A[A.size()-1]-A[0])||Left(A[1]-A[0],p-A[0]))return false; 
	int pos=lower_bound(A.begin(),A.end()-1,p,[&](Point a,Point b){
		a=a-A[0],b=b-A[0];
		return Para(a,b)?a.len()<b.len():Left(b,a);
	})-A.begin();
	return !Left(A[pos]-A[pos-1],p-A[pos-1])&&A[0]<p;
}
//半平面交(HalfPlaneIntersection) <向量左侧> 
inline bool cmpang(Point a,Point b){
	return a.Quad()^b.Quad()?a.Quad()<b.Quad():Left(b,a);
}
inline bool operator <(Line a,Line b){
	return Para(a.v(),b.v())&&(a.v()*b.v()>eps)?Left(a[0]-b[0],b.v()):cmpang(a.v(),b.v());
}
Poly HPI(vector<Line> L){
	L.emplace_back(Point(-inf,-inf),Point(inf,-inf));
	L.emplace_back(Point(inf,-inf),Point(inf,inf));
	L.emplace_back(Point(inf,inf),Point(-inf,inf));
	L.emplace_back(Point(-inf,inf),Point(-inf,-inf));
	vector<Line> q(L.size()+10);
	static int l,r;
	sort(L.begin(),L.end());
	Poly R;
	r=1,q[l=1]=L[0];
	for(int i=1;i<(int)L.size();++i){
		if(Para(q[r].v(),L[i].v()))continue;
		while(l<r&&Left(L[i].v(),Cross(q[r],q[r-1])-L[i][0]))--r;
		while(l<r&&Left(L[i].v(),Cross(q[l],q[l+1])-L[i][0]))++l;
		q[++r]=L[i];
		if(l<r&&Para(q[r].v(),q[r-1].v())){
			return R;
		}
	}
	while(l<r&&Left(q[l].v(),Cross(q[r],q[r-1])-q[l][0]))--r;
	while(l<r&&Left(q[r].v(),Cross(q[l],q[l+1])-q[r][0]))++l;
	if(l==r)return R;
	q[r+1]=q[l];
	for(int i=l;i<=r;++i){
		R.push_back(Cross(q[i],q[i+1]));
	}
	R.erase(unique(R.begin(),R.end()),R.end());
	if(R.size()>1&&R[0]==R.back())R.pop_back();
	return R;
}

//Minkowski
inline Poly operator + (const Poly &A,const Point &p){
	Poly C=A;
	for(auto &t:C)t=t+p;
	return C;
}
inline Poly operator + (const Poly &A,const Poly &B){
	if(A.empty())return B;
	if(B.empty())return A;
	if(A.size()==1)return B+A[0];
	if(B.size()==1)return A+B[0];
	Poly R;
	int i=0,j=0;
	R.push_back(A[0]+B[0]);
	while(true){
		Point vA=A[(i+1)%A.size()]-A[i],vB=B[(j+1)%B.size()]-B[j];
		if(Para(vA,vB)?vA.Quad()==vB.Quad():Left(vA,vB)){
			i=(i+1)%A.size();
		}
		else{
			j=(j+1)%B.size();
		}
		R.push_back(A[i]+B[j]);
		if(!i&&!j)break; 
	}
	R.pop_back();
	return R;
}
int n,m;
void Solve(){
	cin>>n>>m;
	vector<Line> A(n);
	for(int i=0;i<n;++i){
		int a,b,c;
		cin>>a>>b>>c;
		if(!b){
			A[i][0]=Point(-1.0*c/a,0);
			A[i][1]=Point(-1.0*c/a,1);
		}
		else{
			A[i][0]=Point(0,-1.0*c/b);
			A[i][1]=Point(1,(-1.0*c-a)/b);
		}
	}
	if(n>=3){
		cout<<100.0<<"%"<<'\n';
		return;
	}
	double ans=m*m;
	for(int s=0;s<(1<<n);++s){
		vector<Line> L;
		L.emplace_back(Point(0,0),Point(m,0));
		L.emplace_back(Point(m,0),Point(m,m));
		L.emplace_back(Point(m,m),Point(0,m));
		L.emplace_back(Point(0,m),Point(0,0));
		for(int i=0;i<n;++i){
			if(!(s>>i&1)){
				L.emplace_back(A[i][0],A[i][1]);
			}
			else{
				L.emplace_back(A[i][1],A[i][0]);
			}
		}
		ans=min(ans,Area(HPI(L)));
	}
	cout<<100.0*(1.0-ans/(m*m))<<"%"<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.setf(ios::fixed);
	cout.precision(10);
	int T;
	cin>>T;
	while(T--){
		Solve();
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3744kb

input:

1
2 1000
0 1 -750
1 0 -750

output:

93.7500000000%

result:

ok OK!

Test #2:

score: 0
Accepted
time: 3ms
memory: 3848kb

input:

500
1 1000
1 0 -300
1 1000
1 1 -500
1 1000
1 1 -1000
1 2
0 -1 1
1 1
-1 -1 1
1 1000
-866 287 1
1 1
3 -442 1
1 130
-628 558 0
1 868
-297 166 1
1 479
373 3 -96709
1 68
527 -833 0
1 348
-337 954 -109611
1 917
564 2 -449502
1 16
679 -175 0
1 463
138 -961 3
1 361
-951 -12 45113
1 464
-977 622 -35388
1 351...

output:

70.0000000000%
87.5000000000%
50.0000000000%
50.0000000000%
50.0000000000%
83.4294457275%
99.4343891403%
55.5732484076%
72.0534841503%
53.7259258845%
68.3673469388%
50.6786308104%
86.7353844250%
87.1134020619%
92.8193049447%
87.4903513141%
75.4955418490%
99.9392694441%
79.4988172856%
99.7911555184%
...

result:

ok OK!

Test #3:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

50
4000 1000
-866 287 1
-246 141 188157
994 0 -948594
3 -442 1
172 -257 2
-77 -628 557282
-983 -297 165987
-172 -992 4695
961 587 -844056
-981 631 897222
289 1 -184824
-463 493 -336717
954 -110 32323
67 866 -240824
893 -111 -546885
259 -818 385562
906 93 -191311
308 -794 258487
502 -855 -273835
-649...

output:

100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.0000000000%
100.00000000...

result:

ok OK!