QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#755492#7527. Doors of the Wardrobeucup-team138#WA 1ms6092kbC++173.5kb2024-11-16 17:29:252024-11-16 17:29:26

Judging History

This is the latest submission verdict.

  • [2024-11-16 17:29:26]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 6092kb
  • [2024-11-16 17:29:25]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld eps=1e-11;
const ld inf=1e18;
const int maxn=(3e5)+10;
int n,m;
struct node {
    ld x,y;
    friend node operator + (node A,node B) { return (node){A.x+B.x,A.y+B.y}; }
    friend node operator - (node A,node B) { return (node){A.x-B.x,A.y-B.y}; }
    void get() { scanf("%Lf %Lf",&x,&y); }
    friend ld operator * (node A,node B) { return A.x*B.y-A.y*B.x; }
    void print() { printf("(%.5Lf %.5Lf)\n",x,y); }
} p[maxn],d[maxn];
ld ans;
vector<node> v[2];
bool cmp0(node A,node B) {
    if (fabs(A.x-B.x)<eps) return A.y<B.y;
    return A.x<B.x;
}
bool cmp1(node A,node B) {
    if (fabs(A.x-B.x)<eps) return A.y>B.y;
    return A.x<B.x;
}
void insert(vector<node> &vec,node A,int op) {
    if (op==0) {
        while ((int)vec.size()>1&&(A-vec.back())*(vec.back()-vec[(int)vec.size()-2])<0) vec.pop_back();
    } else {
        while ((int)vec.size()>1&&(A-vec.back())*(vec.back()-vec[(int)vec.size()-2])>0) vec.pop_back();
    }
    vec.push_back(A);
}
void chkmin(ld &x,ld y) { if (x>y) x=y; }
void chkmax(ld &x,ld y) { if (x<y) x=y; }
int main() {
    // freopen("qwq.in","r",stdin);
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++) {
        p[i].get();
        d[i].get();
    }
    vector<node> vec(m);
    for (int i=0;i<m;i++) vec[i].get();
    sort(vec.begin(),vec.end(),cmp0);
    for (node &A : vec) insert(v[0],A,0);
    sort(vec.begin(),vec.end(),cmp1);
    for (node &A : vec) insert(v[1],A,1);
    // for (node &A : v[0]) A.print();
    // puts("");
    // for (node &A : v[1]) A.print();
    vec.clear();
    for (int i=n;i>=1;i--) {
        if (fabs(d[i].y)<eps) {
            ld now=p[i].x,l=v[0][0].x,r=v[0].back().x;
            for (node &A : vec) chkmin(l,A.x),chkmax(r,A.x);
            chkmin(l,now),chkmax(r,now);
            ans+=r-l;
            vec.push_back((node){l,p[i].y});
            vec.push_back((node){r,p[i].y});
        } else {
            ld k=-d[i].x/d[i].y;
            ld l=p[i].y-k*p[i].x,r=l;
            for (node &A : vec) chkmin(l,A.y-k*A.x),chkmax(r,A.y-k*A.x);
            for (int op=0;op<=1;++op) {
                int L=0,R=(int)v[op].size()-2;
                while (L<=R) {
                    int mid=(L+R)>>1;
                    ld t1=v[op][mid].y-k*v[op][mid].x;
                    ld t2=v[op][mid+1].y-k*v[op][mid+1].x;
                    chkmin(l,t1),chkmin(l,t2),chkmax(r,t1),chkmax(r,t2);
                    if (fabs(t1-t2)<eps||R-L<=1) break;
                    if (!op) {
                        if (t1>t2) R=mid;
                        else L=mid+1;
                    } else {
                        if (t1<t2) R=mid;
                        else L=mid+1;
                    }
                }
                // for (node &A : v[op]) chkmin(l,A.y-k*A.x),chkmax(r,A.y-k*A.x);
            }
            ans+=(r-l)/sqrtl(k*k+1.0);
            if (fabs(k)<eps) {
                vec.push_back((node){p[i].x,l});
                vec.push_back((node){p[i].x,r});
            } else {
                ld t1=p[i].y-l-k*p[i].x;
                ld t2=p[i].y-r-k*p[i].x;
                t1/=k+1/k;
                t2/=k+1/k;
                vec.push_back((node){p[i].x+t1,p[i].y-t1/k});
                vec.push_back((node){p[i].x+t2,p[i].y-t2/k});
            }
        }
        // vec[(int)vec.size()-2].print();
        // vec.back().print();
    }
    printf("%.15Lf\n",ans);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5928kb

input:

3 4
-3 3 0.6 -0.3
4 -1 1 1
1 -4 1 0
-2 3
2 3
2 -2
-0.5 -2

output:

20.275232907551224

result:

ok answer is 20.2752329075512  (delta 0)

Test #2:

score: 0
Accepted
time: 1ms
memory: 5868kb

input:

5 3
0.5 0.4 1 1
0.5 0.4 3 4
0.5 0.35 1 1
0.4 0.4 1 0
0.5 0.3 0 1
0.5 0.4
0.6 0.4
0.5 0.5

output:

0.859813275223096

result:

ok answer is 0.859813275223096  (delta 1.1102e-16)

Test #3:

score: 0
Accepted
time: 1ms
memory: 5944kb

input:

5 3
0.5 0.4 1 1
0.5 0.4 3 4
0.5 0.35 1 1
0.4 0.4 1 0
0.5 0.3 0 1
0.5 0.4
0.5 0.5
0.6 0.4

output:

0.859813275223096

result:

ok answer is 0.859813275223096  (delta 1.1102e-16)

Test #4:

score: 0
Accepted
time: 1ms
memory: 5872kb

input:

5 12
0.7 -0.3 0 1
0.5 0 1 1
0.5 0.033333333333333 0 1
0.5 0.033333333333333 1 0
0.5 0.05 1 0
0.0 0
0.1 0
0.2 0
0.3 0
0.4 0
0.5 0
0.5 0.1
0.6 0
0.7 0
0.8 0
0.9 0
1.0 0

output:

3.417462120245875

result:

ok answer is 3.41746212024588  (delta 1.2995e-16)

Test #5:

score: 0
Accepted
time: 1ms
memory: 5944kb

input:

5 12
-0.3 0.7 1 0
0 0.5 1 1
0.033333333333333 0.5 1 0
0.033333333333333 0.5 0 1
0.05 0.5 0 1
0 0.6
0 0.4
0.1 0.5
0 0.3
0 0.8
0 0.5
0 0.9
0 1.0
0 0.1
0 0.0
0 0.7
0 0.2

output:

3.417462120245875

result:

ok answer is 3.41746212024588  (delta 1.2995e-16)

Test #6:

score: 0
Accepted
time: 1ms
memory: 5808kb

input:

10 12
0 0 1 1
0.6 0.2 0 1
0.4 0.6 -1 0
0.6 0 -1 1
0 0 0 1
0.4 0.5 1 0
0.5 0.3 1 0
0 0.3 1 0
0.3 0.3 1 0
0.3 0.3 0 1
0.2 0.2
0.6 0.2
0.6 0.6
0.2 0.6
0.2 0.2
0.6 0.2
0.6 0.6
0.2 0.6
0.2 0.2
0.6 0.2
0.6 0.6
0.2 0.6

output:

6.097056274847714

result:

ok answer is 6.09705627484772  (delta 2.9135e-16)

Test #7:

score: 0
Accepted
time: 1ms
memory: 5864kb

input:

11 3
0.4 0.6 -1 1.2
0.8 -0.1 -1 0.1
0.5 1.05 0 1
0.4 1.0 0 1
0.6 1.0 0 1
0.3 0.9 0 1
0.7 0.9 0 1
0.2 0.7 0 1
0.8 0.7 0 1
0.1 0.4 0 1
0.9 0.4 0 1
0 0
1 0
0.5 -0.1

output:

10.181036773720619

result:

ok answer is 10.1810367737206  (delta 0)

Test #8:

score: 0
Accepted
time: 1ms
memory: 5944kb

input:

8 3
-0.762220710020949 0.960848634814740 0.280390347859400 0.959886062419538
-0.543850971093615 0.734414501114893 -0.427256201232584 -0.904130598148465
-0.308587087111148 -0.723868828767586 -0.977369509658100 -0.211539219982217
-0.080679584211341 -0.623872645456952 0.831979117964964 0.55480694594628...

output:

13.026898136401998

result:

ok answer is 13.026898136402  (delta 0)

Test #9:

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

input:

9 3
0.898690498337619 -0.179746197104477 0.999614363528218 -0.027769123646145
0.110351463328162 -0.422616723450085 -0.279788827908685 -0.960061566659912
-0.300252996136536 -0.968309581066027 0.854696098517848 -0.519128673045874
0.952829435906291 0.237672663072341 -0.611183161853922 -0.79148919301923...

output:

19.905002807773680

result:

ok answer is 19.9050028077737  (delta 1.7848e-16)

Test #10:

score: 0
Accepted
time: 1ms
memory: 5864kb

input:

10 3
0.070342089497671 -0.460264862606530 0.571810294945788 -0.820385876642212
0.788475327551128 -0.311212069608293 0.964101929706117 -0.265532425773089
0.366813150247519 0.189414857841604 0.900950396708540 0.433922092858526
-0.025464690043421 0.481042370982425 0.621108238787538 0.783724795901114
0....

output:

21.333621812460929

result:

ok answer is 21.3336218124609  (delta 0)

Test #11:

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

input:

11 3
-0.775122867998075 -0.324462516766419 -0.870185763377592 -0.492723794041812
0.271867294126994 -0.314788596521751 0.875220126295877 -0.483724850019750
0.159838684607629 -0.014674090173325 0.920134803351038 0.391601766673933
-0.208305526915072 0.138678278167128 -0.855854780186333 0.51721619776666...

output:

5.481592390382125

result:

ok answer is 5.48159239038213  (delta 1.6203e-16)

Test #12:

score: 0
Accepted
time: 1ms
memory: 5884kb

input:

12 5
0.316035625860380 0.054167102894646 0.415233195457349 -0.909715006686313
0.012033693255599 -0.517127656466508 -0.998047008109908 0.062467348293813
-0.911778006353474 0.434138159295005 -0.826906371022239 0.562339624748987
0.591762739510491 -0.252317701851837 -0.881901192154716 0.471434287336094
...

output:

20.423831191837825

result:

ok answer is 20.4238311918378  (delta 1.7395e-16)

Test #13:

score: -100
Wrong Answer
time: 1ms
memory: 6092kb

input:

15 7
0.383636462970281 0.091301273291054 -0.178083033367321 -0.984015463916443
0.028282065271478 -0.787867919130403 0.750256053487245 -0.661147377069398
0.149903266403460 0.601903906070213 0.428442456521616 0.903569068444534
0.093087745686689 0.006815105251976 0.803797260834196 -0.594903322797447
-0...

output:

5.729916488179284

result:

wrong answer expected 5.75042689603733, found 5.72991648817928  (delta 0.0035795)