QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799362 | #851. (Almost) Fair Cake-Cutting | CarroT1212 | AC ✓ | 3ms | 4108kb | C++17 | 3.2kb | 2024-12-05 12:05:07 | 2024-12-05 12:05:08 |
Judging History
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!