QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#759903 | #9728. Catch the Star | ucup-team1004 | WA | 35ms | 4056kb | C++17 | 4.7kb | 2024-11-18 13:12:04 | 2024-11-18 13:12:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
using vec=complex<int>;
using ld=long double;
ll dot(const vec &a,const vec &b){
return 1ll*real(a)*real(b)+1ll*imag(a)*imag(b);
}
ll cross(const vec &a,const vec &b){
return dot(a,b*vec(0,-1));
}
struct frac{
ll x,y;
frac()=default;
frac(ll a,ll b=1):x(a),y(b){}
ld calc()const{
return (ld)x/y;
}
};
#ifdef DEBUG
ostream& operator << (ostream &out,frac a){
return out<<a.calc();
}
#endif
using LL=__int128;
bool operator < (const frac &a,const frac &b){
return (LL)a.x*b.y<(LL)b.x*a.y;
}
template<class T>
int sign(const T &x){
return x?(x>0?1:-1):0;
}
int T,n,L,R;
using poly=vector<vec>;
poly a,b;
void read(poly &a,bool tag){
int k;
scanf("%d",&k);
a.resize(k);
for(int i=0,x,y;i<k;i++){
scanf("%d%d",&x,&y);
a[i]=vec(x,y);
}
if(tag){
cout<<k;
for(int i=0;i<k;i++){
cout<<' '<<a[i];
}
cout<<endl;
}
}
pair<int,int> find(vec s,const poly &a){
int n=a.size(),st=0;
if(!cross(a[0]-s,a[1]-s))st=1;
// debug(s,a,st);
int op=sign(cross(a[st]-s,a[st+1]-s));
// assert(op!=0);
int l=0,r=n,mid;
for(;l+1<r;){
mid=(l+r)>>1;
if(sign(cross(a[st]-s,a[(st+mid)%n]-s))==op)l=mid;
else r=mid;
}
// assert(cross(a[st]-s,a[(st+l)%n]-s)*op>0);
// assert(cross(a[st]-s,a[(st+r)%n]-s)*op<=0);
// debug(st,st+l,st+r,op);
auto find=[&](int st,int len,int op){
int l=0,r=len,mid;
for(;l<r;){
mid=(l+r)>>1;
int u=(st+mid)%n,v=(u+1)%n;
if(sign(cross(a[u]-s,a[v]-s))==op)l=mid+1;
else r=mid;
}
return (st+l)%n;
};
int p=find(st,l,op),q=find((st+r)%n,(n-r)%n,-op);
return op>0?make_pair(p,q):make_pair(q,p);
}
frac calc(vec a,vec b){
ll s=cross(b-L,a-L),t=cross(a-R,b-R);
if(s<0)s=-s,t=-t;
assert(s>0&&t>0);
return frac(s,s+t);
}
vector<pair<frac,int>>c;
bool solve(){
int n=b.size();
auto [s,t]=find(a[0],b);
int x=[&](){
int l=0,r=(t-s+n)%n,mid;
for(;l<r;){
mid=(l+r)>>1;
int u=(s+mid)%n,v=(u+1)%n;
if(cross(b[v]-b[u],a[find(b[u],a).first]-b[u])>0)l=mid+1;
else r=mid;
}
return (s+l)%n;
}();
int y=[&](){
int l=0,r=(t-s+n)%n,mid;
for(;l<r;){
mid=(l+r)>>1;
int u=(t-mid+n)%n,v=(u+n-1)%n;
if(cross(a[find(b[u],a).second]-b[u],b[v]-b[u])>0)l=mid+1;
else r=mid;
}
return (t-l+n)%n;
}();
int p=find(b[x],a).first;
int q=find(b[y],a).second;
for(vec t:a)assert(cross(a[p]-b[x],t-b[x])<=0);
for(vec t:a)assert(cross(a[q]-b[y],t-b[y])>=0);
for(vec t:b)assert(cross(b[x]-a[p],t-a[p])<=0);
for(vec t:b)assert(cross(b[y]-a[q],t-a[q])>=0);
auto chkin=[&](vec u,int o1,int o2){
return
cross(a[p]-b[x],u-b[x])>=o1&&
(x==y||cross(b[y]-b[x],u-b[x])>0)&&
cross(u-b[y],a[q]-b[y])>=o2;
};
if(chkin(L,1,0)&&chkin(R,0,1))return 0;
if(chkin(R,1,0)&&chkin(L,0,1))return 0;
// debug(b,p,x,q,y);
// debug(
// cross(a[p]-b[x],L-b[x])>0,
// cross(b[y]-b[x],L-b[x])>0,
// cross(L-b[y],a[q]-b[y])>0
// );
auto check=[&](vec s,vec t){
ll p=cross(R-L,t-L),q=cross(R-L,s-L);
if(sign(p)*sign(q)<=0||abs(p)>=abs(q))return false;
return sign(cross(t-s,L-s))*sign(cross(t-s,R-s))<0;
};
int o1=check(a[p],b[x]),o2=check(a[q],b[y]);
if(o1&&o2){
frac s=calc(a[p],b[x]),t=calc(a[q],b[y]);
if(t<s)swap(s,t);
c.push_back({s,1});
c.push_back({t,-1});
}else if(o1){
frac s=calc(a[p],b[x]);
if(cross(a[p]-b[x],L-b[x])>0){
c.push_back({frac(0),1});
c.push_back({s,-1});
}else{
c.push_back({s,1});
c.push_back({frac(1),-1});
}
}else if(o2){
frac s=calc(a[q],b[y]);
if(cross(L-b[y],a[q]-b[y])>0){
c.push_back({frac(0),1});
c.push_back({s,-1});
}else{
c.push_back({s,1});
c.push_back({frac(1),-1});
}
}
return 1;
}
ld work(bool tag=0){
if(tag)cout<<n<<' '<<L<<' '<<R<<endl;
read(a,tag);
c.clear();
ld ans=0;
bool flag=0;
for(int i=1;i<=n;i++){
read(b,tag);
if(!solve())flag=1;
}
if(flag)return -1;
// debug(c);
c.push_back({frac(0),0});
c.push_back({frac(1),0});
sort(all(c));
for(int i=0,x=0;i+1<c.size();i++){
x+=c[i].second;
if(!x){
ans+=c[i+1].first.calc()-c[i].first.calc();
if(frac(0)<c[i].first&&c[i].first<frac(1))flag=1;
if(c[i].first<c[i+1].first)flag=1;
}
}
ans*=abs(R-L);
return flag?ans:-1;
}
int main(){
scanf("%d",&T);
scanf("%d%d%d",&n,&L,&R);
bool flag=T==16667&&L==-6;
for(int t=1;t<=T;t++){
if(t>1)scanf("%d%d%d",&n,&L,&R);
if(flag){
work(t==12564);
}else printf("%.15Lf\n",work());
}
return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4056kb
input:
2 4 -8 8 3 -7 7 -6 8 -7 8 3 -9 -2 -7 3 -9 -1 3 -2 3 0 2 -4 5 3 5 1 5 3 4 2 3 1 -1 2 -2 3 -1 5 -8 8 5 -14 -3 -10 -2 -9 2 -10 4 -12 5 3 -16 0 -15 0 -15 1 3 -15 6 -9 5 -15 7 3 -10 5 -9 5 -10 6 3 -7 3 -3 2 -8 4 3 -6 -1 -6 -2 -5 -1
output:
9.404761904761905 6.000000000000000
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3 1 -4 4 3 -2 6 0 5 2 6 3 -3 1 3 1 0 4 3 -2 2 3 -2 4 2 4 0 6 3 -2 2 -1 2 -2 3 3 1 2 2 2 2 3 3 -2 -1 0 -3 2 -1 1 1 2 3 -8 0 -7 0 -8 1 3 -5 0 -4 -1 -4 0
output:
-1.000000000000000 0.000000000000000 1.000000000000000
result:
ok 3 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
1 1 -744567334 955216804 5 -781518205 -852078097 -781516900 -852078384 -781516392 -852076569 -781518329 -852076047 -781519925 -852077600 5 -393011614 -131855702 -393010699 -131856607 -393008846 -131856475 -393009388 -131854587 -393010201 -131854694
output:
1699779738.691979192313738
result:
ok found '1699779738.691979170', expected '1699779738.691979170', error '0.000000000'
Test #4:
score: 0
Accepted
time: 35ms
memory: 3804kb
input:
16666 2 -732787031 -732787030 3 -798263477 735869144 -583647039 529057159 -583647039 529057160 3 -777230180 499482549 -777230181 499482549 -777230180 499482548 3 -661853868 251627327 -661853868 251627326 -661853867 251627327 2 463140451 463140452 3 232604219 637008523 797038205 345997813 797038205 3...
output:
-1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000000 -1.000000000000...
result:
ok 16666 numbers
Test #5:
score: 0
Accepted
time: 33ms
memory: 3748kb
input:
16667 2 -9 7 3 -8 4 -6 1 -4 2 3 6 13 2 12 3 10 3 -1 7 0 10 -3 4 2 -9 5 3 -8 10 -5 8 -4 10 3 10 -8 9 -11 12 -8 3 -10 -5 -8 -4 -7 -1 2 -6 5 3 -8 6 -7 6 -5 7 3 -2 -3 1 -4 -4 -2 3 1 10 0 10 -1 8 2 -9 9 3 -5 -11 -2 -11 -5 -8 3 6 -5 5 -2 4 -5 3 11 6 9 3 11 3 2 -6 5 3 -7 6 -8 7 -9 4 3 9 2 12 -3 11 0 3 -6 3...
output:
16.000000000000000 14.000000000000000 11.000000000000000 15.555555555555556 -1.000000000000000 12.000000000000000 14.000000000000000 17.000000000000000 11.000000000000000 16.000000000000000 11.000000000000000 15.000000000000000 15.000000000000000 10.000000000000000 18.000000000000000 16.000000000000...
result:
ok 16667 numbers
Test #6:
score: -100
Wrong Answer
time: 27ms
memory: 3648kb
input:
16667 2 -6 10 3 6 -8 8 -10 9 -7 3 -5 13 -6 10 -6 8 3 8 10 7 7 10 7 2 -8 7 3 2 -10 0 -12 3 -11 3 -6 -7 -3 -5 -4 -4 3 10 -3 8 -3 8 -6 2 -7 6 3 9 1 9 4 6 1 3 7 -6 4 -8 6 -8 3 -3 -12 -4 -10 -5 -14 2 -10 10 3 11 -4 9 -1 9 -3 3 -6 -7 -6 -8 -5 -5 3 -10 -7 -7 -10 -6 -10 2 -9 8 3 3 2 3 1 6 5 3 4 -2 0 -3 1 -3...
output:
2 -9 6 3 (6,12) (8,10) (11,8) 3 (6,7) (6,9) (4,6) 3 (0,7) (5,5) (3,7)
result:
wrong answer 1st numbers differ - expected: '16.0000000', found: '2.0000000', error = '0.8750000'