QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#799362#851. (Almost) Fair Cake-CuttingCarroT1212AC ✓3ms4108kbC++173.2kb2024-12-05 12:05:072024-12-05 12:05:08

Judging History

This is the latest submission verdict.

  • [2024-12-05 12:05:08]
  • Judged
  • Verdict: AC
  • Time: 3ms
  • Memory: 4108kb
  • [2024-12-05 12:05:07]
  • Submitted

answer

#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
using pld=pair<ld,ld>; using cut=pair<pld,pld>;
const int I=1e9;
const ll J=1e18,N=4007;
const ld eps=1e-8,pi=acos(-1);
ll n; ld m;
struct lin { ld a,b,c; } L[N];
pld a[N][4];
cut T[4];
ll cmp(ld x,ld y) { return abs(x-y)<=eps?1:x<y?0:2; }
lin get(pld A,pld B) {
	if (A.x==B.x) { return {1,0,-A.x}; }
	else {
		ld k=(B.y-A.y)/(B.x-A.x);
		return {k,-1,A.y-k*A.x};
	}
}
bool chk(pld A) { return -eps<A.x&&A.x<m+eps&&-eps<A.y&&A.y<m+eps; }
ld dst(pld A,pld B) { return sqrtl((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)); }
ld dst(pld A,lin l) { return fabs(l.a*A.x+l.b*A.y+l.c)/sqrtl(l.a*l.a+l.b*l.b); }
ld operator * (pld x,pld y) { return x.x*y.y-x.y*y.x; }
pld operator * (pld x,ld y) { return {x.x*y,x.y*y}; }
pld operator + (pld x,pld y) { return {x.x+y.x,x.y+y.y}; }
pld operator - (pld x,pld y) { return {x.x-y.x,x.y-y.y}; }
cut get(lin x) {
	if (x.b==0) return {{x.c/-x.a,0},{x.c/-x.a,1}};
	return {{0,x.c/-x.b},{1,(x.c+x.a)/-x.b}};
}
pld its(cut x,cut y) {
	pld xx=x.y-x.x,yy=y.y-y.x,zz=x.y-y.y;
	if (xx*yy==0) return {-1,0};
	else {
		ld t=(zz*yy)/(xx*yy);
		return x.y-xx*t;
	}
}
ld S(pld A,pld B,pld C) { return fabs((C-A)*(B-A)/2); }
ld S(vector<pld> v) { ld ret=0; for (ll i=2;i<v.size();i++) ret+=S(v[0],v[i-1],v[i]); return ret; }
void mian() {
	#define bao return printf("100.000000%%\n"),void()
	scanf("%lld%Lf",&n,&m);
	vector<pair<pld,ll>> v;
	v.pb({{0,0},0}),v.pb({{m,0},0}),v.pb({{m,m},0}),v.pb({{0,m},0});
	for (ll i=0;i<4;i++) T[i]={v[i].x,v[(i+1)%4].x};
	for (ll i=1;i<=n;i++) scanf("%Lf%Lf%Lf",&L[i].a,&L[i].b,&L[i].c);
	if (n>=3) bao;
	else {
		pld A=its(get(L[1]),get(L[2]));
		if (n==2&&!chk(A)) bao;
		for (ll i=1;i<=n;i++) {
			ll sz=0;
			for (ll j=0;j<4;j++) {
				pld x=its(T[j],get(L[i]));
//				printf("%.1Lf %.1Lf\n",x.x,x.y);
				if (chk(x)) a[i][sz++]=x;
			}
//			for (ll j=0;j<sz;j++) printf(" %.1Lf %.1Lf ",a[i][j].x,a[i][j].y); printf("\n");
			sort(a[i],a[i]+sz),sz=unique(a[i],a[i]+sz,[](pld x,pld y){return fabs(x.x-y.x)<eps&&fabs(x.y-y.y)<eps;})-a[i];
//			for (ll j=0;j<sz;j++) printf("  %.1Lf %.1Lf ",a[i][j].x,a[i][j].y); printf("\n");
			if (sz<=1) bao;
			assert(sz==2);
			for (ll j=0;j<2;j++) v.pb({a[i][j],1});
		}
		sort(v.begin(),v.end(),[](auto x,auto y){
			ld kx=atan2(x.x.y,x.x.x),ky=atan2(y.x.y,y.x.x);
			if (kx!=ky) return kx<ky;
			else return (pld){x.x.x,-x.x.y}<(pld){y.x.x,-y.x.y};
		});
//		for (auto i:v) printf("= %Lf %Lf %lld\n",i.x.x,i.x.y,i.y);
		ld ans=J;
		for (ll l=0;l<v.size();l++) if (v[l].y) {
			for (ll r=(l+1)%v.size();;r=(r+1)%v.size()) if (v[r].y) {
				vector<pld> ret;
				if (n==2) ret.pb(A);
				for (ll k=l;;k=(k+1)%v.size()) { ret.pb(v[k].x); if (k==r) break; }
//				for (pld i:ret) printf(" %.1Lf %.1Lf |",i.x,i.y); printf("\n");
				ans=min(ans,S(ret));
				break;
			}
		}
		printf("%.6Lf%%\n",(m*m-ans)/(m*m)*100);
	}
}
bool ORY; int main() {
//	while (1)
	int t; for (scanf("%d",&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3916kb

input:

1
2 1000
0 1 -750
1 0 -750

output:

93.750000%

result:

ok OK!

Test #2:

score: 0
Accepted
time: 2ms
memory: 3984kb

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.000000%
87.500000%
50.000000%
50.000000%
50.000000%
83.429446%
99.434389%
55.573248%
72.053484%
53.725926%
68.367347%
50.678631%
86.735384%
87.113402%
92.819305%
87.490351%
75.495542%
99.939269%
79.498817%
99.791156%
100.000000%
99.967926%
71.862629%
87.212627%
99.999999%
52.507599%
95.787352%
98...

result:

ok OK!

Test #3:

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

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.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
100.000000%
...

result:

ok OK!