QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#736011#5448. 另一个欧拉数问题Qingyu0 253ms3688kbC++236.4kb2024-11-11 23:32:002024-11-11 23:32:00

Judging History

你现在查看的是最新测评结果

  • [2024-11-11 23:32:00]
  • 评测
  • 测评结果:0
  • 用时:253ms
  • 内存:3688kb
  • [2024-11-11 23:32:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define mp make_pair

int sgn(ll a) {
    return a<0?-1:(a>0);
}
int cmp(ll a,ll b) {
    return sgn(a-b);
}
struct P {
    ll x,y;
    P() {}
    P(ll _x,ll _y):x(_x),y(_y) {}
    P operator +(P p) { return {x+p.x,y+p.y};}
    P operator -(P p) { return {x-p.x,y-p.y};}
    bool operator < (P p) const {
        int c=cmp(x,p.x);
        if (c) return c==-1;
        return cmp(y,p.y)==-1;
    }
    bool operator > (P p) const {
        int c=cmp(x,p.x);
        if (c) return c==1;
        return cmp(y,p.y)==1;
    }
    bool operator ==(P o) const {
        return cmp(x,o.x)==0 && cmp(y,o.y)==0;
    }
    ll det(P p) {
        return x*p.y-y*p.x;
    }
    void print() {
        printf("(%lld,%lld) ",x,y);
    }
};
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sgn(cross(p1,p2,p3))

struct CH {
    int n;
    vector<P> ps,lower,upper;
    P operator[](int i) { return ps[i];}
    void init(vector<P> _ps) {
        ps=_ps;
        n=ps.size();
        rotate(ps.begin(),min_element(ps.begin(),ps.end()),
        ps.end());
        int at=max_element(ps.begin(),ps.end())-ps.begin();
        lower=vector<P>(ps.begin(),ps.begin()+at+1);
        upper=vector<P>(ps.begin()+at,ps.end());
        upper.pb(ps[0]);
    }
    void update_tangent(P p,int id,int &a,int &b) {
        if (crossOp(p,ps[a],ps[id])>0) a=id;
        if (crossOp(p,ps[b],ps[id])<0) b=id;
    }
    void binary_search(int l,int r,P p,int &a,int &b) {
        if (l==r) return;
        update_tangent(p,l%n,a,b);
        int sl=crossOp(p,ps[l%n],ps[(l+1)%n]);
        while (l+1<r) {
            int m=(l+r)/2;
            if (crossOp(p,ps[m%n],ps[(m+1)%n]) == sl)
                l=m;
            else r=m;
        }
        update_tangent(p,r%n,a,b);
    }
    void get_tangent(P p,int &a,int &b) {
        a=b=0;
        int id=lower_bound(lower.begin(),lower.end(),p)-lower.begin();
        binary_search(0,id,p,a,b);
        binary_search(id,lower.size(),p,a,b);
        id=lower_bound(upper.begin(),upper.end(),p,greater<P>())-upper.begin();
        binary_search((int)lower.size()-1,(int)lower.size()-1+id,p,a,b);
        binary_search((int)lower.size()-1+id,(int)lower.size()-1+upper.size(),p,a,b);
    }
};
typedef long double db;
struct frac {
    ll a,b;
    frac() {}
    frac(ll x):a(x),b(1) {}
    frac(ll x,ll y):a(x),b(y) {};
    db eval() { return (db)a/b;}
};
typedef __int128 i128;
bool operator == (frac a,frac b) {
    return (i128)a.a*b.b==(i128)b.a*a.b;
}
bool operator < (frac a,frac b) {
    return (i128)a.a*b.b<(i128)b.a*a.b;
}
bool operator > (frac a,frac b) {
    return (i128)a.a*b.b<(i128)b.a*a.b;
}

db diff(frac a,frac b) {
    i128 p1=(i128)b.a*a.b-(i128)a.a*b.b;
    i128 p2=(i128)a.b*b.b;
    return 1.*p1/p2;
}
struct poly {
    int n;
    vector<P> p;
    void read() {
        scanf("%d",&n);
        p=vector<P>(n);
        for (int i=0;i<n;i++) {
            int x,y;
            scanf("%d%d",&x,&y);
            p[i]=P(x,y);
        }
    }
};
int n,l,r;
void solve() {
    scanf("%d%d%d",&n,&l,&r);
    poly s,m;
    vector<pair<frac,int>> evt;
    s.read();
    CH ch;
    ch.init(s.p);
    for (int i=0;i<n;i++) {
        m.read();
        P d1,d2;
        P s1,t1,s2,t2;
        frac L(l),R(r);
        int q1=-1,q2=-1;
        for (int j=0;j<m.n;j++) {
            auto u=m.p[j];
            int a=-1,b=-1;
            ch.get_tangent(u,a,b);
            swap(a,b);
            if (j==0) {
                P dir=ch[a]-u;
                d1=dir; s1=u; t1=ch[a];
                q1=j;
                dir=ch[b]-u;
                d2=dir; s2=u; t2=ch[b];
                q2=j;
            } else {
                P dir1=ch[a]-u;
                if (dir1.det(d1)>0) {
                    d1=dir1; s1=u; t1=ch[a];                
                    q1=j;
                }
                P dir2=ch[b]-u;
                if (d2.det(dir2)>0) {
                    d2=dir2; s2=u; t2=ch[b];
                    q2=j;
                }
            }
            // (p-t1).det(s1-t1) >= 0
            // (p-t2).det(s2-t2) <= 0
        }
        auto add=[&](P z,ll y) {
            //x*z.y>=y
            ll a=z.y;
            //printf("x * %lld >= %lld\n",z.y,y);
            if (a==0) {
                if (y>=0) L=frac(r),R=frac(l);
                return;
            }
            if (a>0) L=max(L,frac(y,a));
            else R=min(R,frac(-y,-a));
        };
        add(t1-s1,t1.det(t1-s1));
        add(s2-t2,t2.det(s2-t2));
        auto chk=[&](P p1,P p2,frac x) {
            P c=(p2-p1);
            i128 v1=i128(c.x*(-p1.y)+c.y*p1.x)*x.b;
            return v1>=(i128)c.y*x.a;
        };
        if (L<R) {
            //printf("%lld/%lld %lld/%lld\n",L.a,L.b,R.a,R.b);
            bool ot=1;
            for (int j=q2;j!=q1;j=(j+1)%m.n) {
                P v1=m.p[j],v2=m.p[(j+1)%m.n];
                ot&=chk(v1,v2,L);
            }
            if (ot) {
                //puts("!!!!!!!");
                evt.pb(mp(L,1));
                evt.pb(mp(R,-1));
            }
        }
        //printf("tagent: "); s1.print(); t1.print(); s2.print(); t2.print(); puts("");
        //printf("%d %d\n",q2,q1);
    }
    evt.pb(mp(frac(l),-1000));
    evt.pb(mp(frac(r),1000));
    sort(evt.begin(),evt.end());
    int cur=1000;
    bool vis=0;
    db ans=0;
    for (int i=0;i+1<evt.size();i++) {
        auto [pa,pb]=evt[i];
        auto [qa,qb]=evt[i+1];
        cur+=pb;
        if (cur==0) {
            if (pa==qa&&(pa==frac(l)||pa==frac(r))) continue;
            vis=1;
            ans+=diff(pa,qa);
        }
    }
    if (!vis) puts("-1");
    else printf("%.15f\n",(double)ans);
}

int _;
int main() {
    for (scanf("%d",&_);_;_--) {
        solve();
    }   
}
/*
x * 4 >= 59
x * 5 >= 75
tagent: (-15,1) (-14,-3) (-15,0) (-12,5) 
x * 0 >= 15
x * -1 >= 3
-8/1 -3/1
tagent: (-9,5) (-12,5) (-15,6) (-12,5) 
x * 0 >= 10
x * -3 >= -25
-8/1 8/1
tagent: (-10,5) (-12,5) (-10,5) (-9,2) 
x * -2 >= 1
x * -6 >= -56
-8/1 -1/2
tagent: (-7,3) (-12,5) (-8,4) (-10,-2) 
x * -6 >= -44
x * -2 >= -4
-8/1 4/2
tagent: (-6,-2) (-10,4) (-6,-1) (-14,-3) 
-1
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

584 1985 1017 186
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 125ms
memory: 3652kb

input:

1 199913 100055 1
1

output:

-1

result:

wrong answer 1st numbers differ - expected: '856065368', found: '-1'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 253ms
memory: 3688kb

input:

2 199984 99989 1
1 1

output:

-1
-1

result:

wrong answer 1st numbers differ - expected: '169573504', found: '-1'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%