QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#736011 | #5448. 另一个欧拉数问题 | Qingyu | 0 | 253ms | 3688kb | C++23 | 6.4kb | 2024-11-11 23:32:00 | 2024-11-11 23:32:00 |
Judging History
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%