QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#736001 | #5448. 另一个欧拉数问题 | Qingyu | 0 | 0ms | 0kb | C++23 | 5.5kb | 2024-11-11 23:27:56 | 2024-11-11 23:27:57 |
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define sz(a) ((int) (a).size())
#define ll long long
#define vi vector<int>
#define me(a, x) memset(a, x, sizeof(a))
#define pb emplace_back
#define mkp make_pair
using namespace std;
const int N = 1e6 + 7, mod = 1e9 + 7;
struct vec {
ll x, y;
vec(ll X = 0, ll Y = 0) {
x = X;
y = Y;
}
};
vec operator + (vec a, vec b) {
return vec(a.x + b.x, a.y + b.y);
}
vec operator - (vec a, vec b) {
return vec(a.x - b.x, a.y - b.y);
}
__int128 operator * (vec a, vec b) {
return (__int128)a.x * b.x + (__int128)a.y * b.y;
}
int cmp_ct(vec a, vec b, vec c){
// printf("ct %lld %lld %lld %lld %lld %lld\n",a.x,a.y,b.x,b.y,c.x,c.y);
vec v1=vec(a.y-b.y,b.x-a.x);
vec v2=vec(c.x-b.x,c.y-b.y);
if(v1*v2>0) return 1; //ccw
else return 0; //cw
}
bool cmp_ct_0(vec a, vec b, vec c){
// printf("ct %lld %lld %lld %lld %lld %lld\n",a.x,a.y,b.x,b.y,c.x,c.y);
vec v1=vec(a.y-b.y,b.x-a.x);
vec v2=vec(c.x-b.x,c.y-b.y);
if(v1*v2==0) return 1; //ccw
else return 0; //cw
}
int n;
ll l, r;
vector<vec>getin() {
int k;
cin >> k;
vector<vec>qwq;
while(k--) {
ll x, y;
cin >> x >> y;
qwq.pb(vec(x, y));
}
return qwq;
}
vector<vec>star;
#define db long double
struct fs{
ll fz,fm;
fs(ll ffz,ll ffm)
{
fz=ffz,fm=ffm;
}
db getdouble(){assert(fm!=0);return 1.0L*fz/fm;}
bool operator<(const fs&t)const
{
return (__int128)fz*t.fm<(__int128)fm*t.fz;
}
bool operator>(const fs&t)const
{
return (__int128)fz*t.fm>(__int128)fm*t.fz;
}
bool operator<=(const fs&t)const
{
return (__int128)fz*t.fm<=(__int128)fm*t.fz;
}
void print()
{
printf("%lld %lld ",fz,fm);
}
};
const fs fs_inf(-2e18,1);
int buc[1<<20];
int invalid_count;
void Main() {
cin >> n >> l >> r;
star=getin();
int sz=star.size();
reverse(star.begin(),star.end());
vector<vec> star1;
for(int i=1; i<sz; ++i) star1.push_back(star[i]);
star1.push_back(star[0]);
// printf("%d\n",sz);
// for(auto i:star)
// printf("%lld %lld\n",i.x,i.y);
// star.push_back(star[0]);
int zak=0;
vector<pair<fs,int>> sweep;
const ll inf=2e18;
L(t, 1, n) {
fs LL=fs(-inf,1);
fs RR=fs(inf,1);
vector<vec> u = getin();
auto r = star[0];
for(auto p : u) {
int sdt=cmp_ct(p,star[sz-1],star[0]);
if(cmp_ct_0(p,star[sz-1],star[0])) star.swap(star1),sdt=cmp_ct(p,star[sz-1],star[0]);
// printf("sdt %d\n",sdt);
int l=1,r=sz-1,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
int res=cmp_ct(p,star[mid-1],star[mid]);
// printf("bin %d %d\n",mid,res);
if((res==1)==(sdt==1))
{
res=cmp_ct(p,star[0],star[mid]);
}
if((res==1)==(sdt==1))
{
ans=mid,l=mid+1;
}
else r=mid-1;
}
// printf("try %lld %lld ",p.x,p.y);
// printf("get %lld %lld ",star[ans].x,star[ans].y);
int ans1=0;
l=1,r=sz-1;
while(l<=r)
{
int mid=(l+r)>>1;
int res=cmp_ct(p,star[mid-1],star[mid]);
if((res==1)==(sdt==1))
{
res=cmp_ct(p,star[0],star[mid]);
}
else res=sdt;
if((res==1)==(sdt==1))
{
ans1=mid,l=mid+1;
}
else r=mid-1;
}
// printf("GET %lld %lld\n",star[ans1].x,star[ans1].y);
if(cmp_ct(p,star[ans],star[ans1])==0) swap(ans,ans1);
//p->ans, we want left(ccw)
auto A=p,B=star[ans];
++zak;
fs LLL=fs(-inf,1);
fs RRR=fs(inf,1);
auto addseg=[&](){
if(A.y==B.y)
{
if((A.y>0)==(A.x<B.x))
{
// sweep.push_back({fs_inf,zak});
// LLL=max(LLL,)
}
}
else
{
//intersect with X-axis
auto [x1,y1]=A;
auto [x2,y2]=B;
// printf("%lld %lld %lld %lld\n",x1,y1,x2,y2);
swap(x1,y1);
swap(x2,y2);
if(x1>x2) swap(x1,x2),swap(y1,y2);
auto intersect=fs(y1*(x2-x1)-x1*(y2-y1),x2-x1);
// printf("%lld %lld %lld %lld %lld %lld\n",x1,y1,x2,y2,intersect.fz,intersect.fm);
if(cmp_ct(A,B,vec(inf,0)))
{
if(intersect<RRR) RRR=intersect;
// sweep.push_back({fs_inf,zak});
// sweep.push_back({intersect,-zak});
}
else
{
if(intersect>LLL) LLL=intersect;
// sweep.push_back({intersect,zak});
}
}};
// printf("%d %lld %lld\n",zak,A.x,A.y);
// printf("+ %lld %lld\n",B.x,B.y);
addseg();
A=star[ans1],B=p;
addseg();
if(LL>LLL) LL=LLL;
if(RR<RRR) RR=RRR;
// printf("+ %lld %lld\n",A.x,A.y);
//ans1->p, we want left(ccw)
}
++zak;
sweep.push_back({LL,zak});
sweep.push_back({RR,-zak});
}
// return ;
// for(auto [A,B]:sweep)
// {
// A.print();
// printf(" %d\n",B);
// }
sweep.push_back({fs(l,1),0});
sweep.push_back({fs(r,1),0});
sort(sweep.begin(),sweep.end());
fs last=fs(-inf,1);
bool exist=0;
db ans=0;
for(auto [t,id]:sweep)
{
//time calc
bool dontcalc=0;
if(t<=fs(l,1)){last=t;dontcalc=1;}
if(invalid_count==0&&!dontcalc)
exist=1,
// printf("%.3Lf %.3Lf\n",tast.getdouble(),t.getdouble()),
ans=(ans+t.getdouble()-last.getdouble());
if(id<0)
{
if(buc[-id]--==1) --invalid_count;
}
if(id>0)
{
if(++buc[id]==1) ++invalid_count;
}
// printf("%lld %lld %d %d %.2Lf\n",t.fz,t.fm,id,invalid_count,ans);
last=t;
if(t<=fs(r,1)&&fs(r,1)<=t) break;
}
if(exist==0) puts("-1");
else printf("%.15Lf\n",ans);
for(int i=1; i<=zak; ++i) buc[i]=0;
invalid_count=0;
zak=0;
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t; while(t--) Main();
return 0;
}
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
Time Limit Exceeded
Test #11:
score: 0
Time Limit Exceeded
input:
1 199913 100055 1 1
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #21:
score: 0
Time Limit Exceeded
input:
2 199984 99989 1 1 1
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%