QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54254 | #2290. Kinking Cables | KING_UT# | AC ✓ | 7ms | 3880kb | C++20 | 2.8kb | 2022-10-07 17:45:29 | 2022-10-07 17:45:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
using uint=unsigned;
using ull=unsigned ll;
#define rng(i, a, b) for(int i=(int)a;i<(int)b;i++)
#define rep(i,n) rng(i,0,n)
using ld=long double;
const ld eps=1e-9;
bool is0(ld x){ return -eps<=x&&x<=eps; }
template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;
using vi=vc<int>;
#define a first
#define b second
using vi=vc<int>;
#define pb push_back
#define eb emplace_back
template<class t,class u>bool chmax(t &a,u b){
if(a <b){a=b;return true;}
else return false;
}
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t>void mkuni(vc<t>&vs){
sort(all(vs));
vs.erase(unique(all(vs)),vs.ed);
}
template<class t>int lwb(const vc<t>&vs,t a){
return lower_bound(all(vs),a)-vs.bg;
}
const uint mod=1000000007;
struct mint{
uint v;
mint(ll vv=0){s(vv%mod+mod);}
mint&s(uint vv){
v=vv<mod?vv:vv-mod;
return *this;
}
mint operator-()const{return mint()-*this;}
mint&operator+=(const mint&r){return s(v+r.v);}
mint&operator-=(const mint&r){return s(v+mod-r.v);}
mint&operator*=(const mint&r){v=(ull)v*r.v%mod;return *this;}
mint&operator/=(const mint&r){return *this*=r.inv();}
mint operator+(const mint&r)const{return mint(*this)+=r;}
mint operator-(const mint&r)const{return mint(*this)-=r;}
mint operator*(const mint&r)const{return mint(*this)*=r;}
mint operator/(const mint&r)const{return mint(*this)/=r;}
mint pow(ll n)const{
if(n<0)return inv().pow(-n);
mint res(1),x(*this);
while(n){
if(n&1)res*=x;
x*=x;
n>>=1;
}
return res;
}
mint inv()const{return pow(mod-2);}
bool operator<(const mint&r)const{return v<r.v;}
bool operator==(const mint&r)const{return v==r.v;}
};
using pt=complex<ld>;
#define x real()
#define y imag()
ld dist(pt a,pt b){
return sqrt(norm(a-b));
}
int sgn(ld a){return a<-eps?-1:(a>eps?1:0);}
int sgn(ld a,ld b){return sgn(a-b);}
void slv(){
int n,m;cin>>n>>m;
ld tar;cin>>tar;
vc<pt> ls;
ls.eb(0,0);
int i=0,j=0;
rep(step,100000){
if(step%4==0){
j=m;
}else if(step%4==1){
i++;
}else if(step%4==2){
j=0;
}else{
i++;
}
pt cur=ls.back();
pt nx=pt(i,j);
auto calc=[&](ld t){
pt z=cur*(1-t)+nx*t;
return dist(cur,z)+dist(z,pt(n,m));
};
if(sgn(tar,calc(1))<=0){
ld lw=0,up=1;
rep(_,60){
const ld mid=(lw+up)/2;
if(sgn(tar,calc(mid))<=0)up=mid;
else lw=mid;
}
ls.pb(cur*(1-up)+nx*up);
ls.eb(n,m);
break;
}else{
tar-=dist(cur,nx);
ls.pb(nx);
}
}
cout<<si(ls)<<endl;
for(auto v:ls){
cout<<v.x<<" "<<v.y<<endl;
}
if(0){
ld sum=0;
rep(k,si(ls)-1)sum+=dist(ls[k],ls[k+1]);
cerr<<sum<<endl;
}
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
cout<<fixed<<setprecision(10);
slv();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
79 78 1980.7712136406
output:
49 0.0000000000 0.0000000000 0.0000000000 78.0000000000 1.0000000000 78.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 78.0000000000 3.0000000000 78.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 78.0000000000 5.0000000000 78.0000000000 5.000...
result:
ok correct
Test #2:
score: 0
Accepted
time: 2ms
memory: 3800kb
input:
33 65 1947.7601065763
output:
61 0.0000000000 0.0000000000 0.0000000000 65.0000000000 1.0000000000 65.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 65.0000000000 3.0000000000 65.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 65.0000000000 5.0000000000 65.0000000000 5.000...
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
51 51 555.0803652025
output:
21 0.0000000000 0.0000000000 0.0000000000 51.0000000000 1.0000000000 51.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 51.0000000000 3.0000000000 51.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 51.0000000000 5.0000000000 51.0000000000 5.000...
result:
ok correct
Test #4:
score: 0
Accepted
time: 3ms
memory: 3800kb
input:
49 2 67.3588717350
output:
21 0.0000000000 0.0000000000 0.0000000000 2.0000000000 1.0000000000 2.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 2.0000000000 3.0000000000 2.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 2.0000000000 5.0000000000 2.0000000000 5.000000000...
result:
ok correct
Test #5:
score: 0
Accepted
time: 4ms
memory: 3856kb
input:
37 48 1713.3643608504
output:
70 0.0000000000 0.0000000000 0.0000000000 48.0000000000 1.0000000000 48.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 48.0000000000 3.0000000000 48.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 48.0000000000 5.0000000000 48.0000000000 5.000...
result:
ok correct
Test #6:
score: 0
Accepted
time: 3ms
memory: 3764kb
input:
51 79 820.1218304546
output:
21 0.0000000000 0.0000000000 0.0000000000 79.0000000000 1.0000000000 79.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 79.0000000000 3.0000000000 79.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 79.0000000000 5.0000000000 79.0000000000 5.000...
result:
ok correct
Test #7:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
6 8 37.5338494218
output:
9 0.0000000000 0.0000000000 0.0000000000 8.0000000000 1.0000000000 8.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 8.0000000000 3.0000000000 8.0000000000 3.0000000000 3.1602695488 6.0000000000 8.0000000000
result:
ok correct
Test #8:
score: 0
Accepted
time: 2ms
memory: 3820kb
input:
5 5 7.1908428511
output:
3 0.0000000000 0.0000000000 0.0000000000 0.3898547298 5.0000000000 5.0000000000
result:
ok correct
Test #9:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
5 4 8.3927665498
output:
3 0.0000000000 0.0000000000 0.0000000000 3.3507961345 5.0000000000 4.0000000000
result:
ok correct
Test #10:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
4 2 6.4617533647
output:
5 0.0000000000 0.0000000000 0.0000000000 2.0000000000 1.0000000000 2.0000000000 1.0000000000 1.5690426155 4.0000000000 2.0000000000
result:
ok correct
Test #11:
score: 0
Accepted
time: 4ms
memory: 3844kb
input:
91 87 4830.8473359767
output:
109 0.0000000000 0.0000000000 0.0000000000 87.0000000000 1.0000000000 87.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 87.0000000000 3.0000000000 87.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 87.0000000000 5.0000000000 87.0000000000 5.00...
result:
ok correct
Test #12:
score: 0
Accepted
time: 5ms
memory: 3852kb
input:
90 90 5088.9280941138
output:
113 0.0000000000 0.0000000000 0.0000000000 90.0000000000 1.0000000000 90.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 90.0000000000 3.0000000000 90.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 90.0000000000 5.0000000000 90.0000000000 5.00...
result:
ok correct
Test #13:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
90 92 7004.0153432299
output:
153 0.0000000000 0.0000000000 0.0000000000 92.0000000000 1.0000000000 92.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 92.0000000000 3.0000000000 92.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 92.0000000000 5.0000000000 92.0000000000 5.00...
result:
ok correct
Test #14:
score: 0
Accepted
time: 3ms
memory: 3692kb
input:
91 83 1879.3819547895
output:
45 0.0000000000 0.0000000000 0.0000000000 83.0000000000 1.0000000000 83.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 83.0000000000 3.0000000000 83.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 83.0000000000 5.0000000000 83.0000000000 5.000...
result:
ok correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
3 81 199.2077743610
output:
5 0.0000000000 0.0000000000 0.0000000000 81.0000000000 1.0000000000 81.0000000000 1.0000000000 22.4131765345 3.0000000000 81.0000000000
result:
ok correct
Test #16:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
4 89 288.5915130114
output:
9 0.0000000000 0.0000000000 0.0000000000 89.0000000000 1.0000000000 89.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 89.0000000000 3.0000000000 89.0000000000 3.0000000000 79.7311374867 4.0000000000 89.0000000000
result:
ok correct
Test #17:
score: 0
Accepted
time: 4ms
memory: 3772kb
input:
95 3 175.9210001082
output:
55 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 3.0000000000 3.0000000000 3.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 3.0000000000 5.0000000000 3.0000000000 5.000000000...
result:
ok correct
Test #18:
score: 0
Accepted
time: 3ms
memory: 3872kb
input:
84 4 310.3037172015
output:
115 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 4.0000000000 3.0000000000 4.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 4.0000000000 5.0000000000 4.0000000000 5.00000000...
result:
ok correct
Test #19:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
2 2 2.8284271248
output:
3 0.0000000000 0.0000000000 0.0000000000 0.0000000000 2.0000000000 2.0000000000
result:
ok correct
Test #20:
score: 0
Accepted
time: 7ms
memory: 3764kb
input:
100 100 10000.0000000000
output:
199 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 100.000000000...
result:
ok correct
Test #21:
score: 0
Accepted
time: 6ms
memory: 3852kb
input:
100 100 9999.2500000000
output:
199 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 100.000000000...
result:
ok correct
Test #22:
score: 0
Accepted
time: 3ms
memory: 3764kb
input:
100 100 2723.8981892905
output:
53 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 100.0000000000...
result:
ok correct
Test #23:
score: 0
Accepted
time: 6ms
memory: 3760kb
input:
100 100 8994.4904261819
output:
179 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 100.000000000...
result:
ok correct
Test #24:
score: 0
Accepted
time: 2ms
memory: 3816kb
input:
100 100 881.4998747190
output:
17 0.0000000000 0.0000000000 0.0000000000 100.0000000000 1.0000000000 100.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 100.0000000000 3.0000000000 100.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 100.0000000000 5.0000000000 100.0000000000...
result:
ok correct
Test #25:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
88 94 8266.2500000000
output:
177 0.0000000000 0.0000000000 0.0000000000 94.0000000000 1.0000000000 94.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 94.0000000000 3.0000000000 94.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 94.0000000000 5.0000000000 94.0000000000 5.00...
result:
ok correct
Test #26:
score: 0
Accepted
time: 6ms
memory: 3776kb
input:
75 37 2772.0000000000
output:
145 0.0000000000 0.0000000000 0.0000000000 37.0000000000 1.0000000000 37.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 37.0000000000 3.0000000000 37.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 37.0000000000 5.0000000000 37.0000000000 5.00...
result:
ok correct
Test #27:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
48 39 62.0000000000
output:
3 0.0000000000 0.0000000000 0.0000000000 0.4130434756 48.0000000000 39.0000000000
result:
ok correct
Test #28:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
98 94 135.9000000000
output:
3 0.0000000000 0.0000000000 0.0000000000 0.3437947462 98.0000000000 94.0000000000
result:
ok correct
Test #29:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
90 81 7290.0000000000
output:
177 0.0000000000 0.0000000000 0.0000000000 81.0000000000 1.0000000000 81.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 81.0000000000 3.0000000000 81.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 81.0000000000 5.0000000000 81.0000000000 5.00...
result:
ok correct
Test #30:
score: 0
Accepted
time: 2ms
memory: 3848kb
input:
90 81 121.0826164250
output:
3 0.0000000000 0.0000000000 0.0000000000 0.0000000010 90.0000000000 81.0000000000
result:
ok correct
Test #31:
score: 0
Accepted
time: 4ms
memory: 3700kb
input:
34 99 3366.0000000000
output:
69 0.0000000000 0.0000000000 0.0000000000 99.0000000000 1.0000000000 99.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 99.0000000000 3.0000000000 99.0000000000 3.0000000000 0.0000000000 4.0000000000 0.0000000000 4.0000000000 99.0000000000 5.0000000000 99.0000000000 5.000...
result:
ok correct
Test #32:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
34 99 104.6756896330
output:
3 0.0000000000 0.0000000000 0.0000000000 0.0000000000 34.0000000000 99.0000000000
result:
ok correct
Test #33:
score: 0
Accepted
time: 3ms
memory: 3748kb
input:
3 3 5.9999
output:
3 0.0000000000 0.0000000000 0.0000000000 2.9998999973 3.0000000000 3.0000000000
result:
ok correct
Test #34:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
3 3 6.0
output:
3 0.0000000000 0.0000000000 0.0000000000 2.9999999990 3.0000000000 3.0000000000
result:
ok correct
Test #35:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
3 3 6.0001
output:
5 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 2.9999000035 3.0000000000 3.0000000000
result:
ok correct
Test #36:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
4 4 13.999998
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000011117 4.0000000000 4.0000000000
result:
ok correct
Test #37:
score: 0
Accepted
time: 2ms
memory: 3800kb
input:
4 4 14.0
output:
5 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000006 4.0000000000 4.0000000000
result:
ok correct
Test #38:
score: 0
Accepted
time: 2ms
memory: 3804kb
input:
4 4 14.000002
output:
6 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 1.0000049975 0.0000000000 4.0000000000 4.0000000000
result:
ok correct
Test #39:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
4 4 15.123104
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 2.7807730140 4.0000000000 4.0000000000
result:
ok correct
Test #40:
score: 0
Accepted
time: 3ms
memory: 3752kb
input:
4 4 15.123106
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 2.7807771851 4.0000000000 4.0000000000
result:
ok correct
Test #41:
score: 0
Accepted
time: 3ms
memory: 3848kb
input:
4 4 15.123108
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 2.7807813563 4.0000000000 4.0000000000
result:
ok correct
Test #42:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
4 4 14.593385
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 0.9261994750 4.0000000000 4.0000000000
result:
ok correct
Test #43:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
4 4 14.593387
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 0.9262118351 4.0000000000 4.0000000000
result:
ok correct
Test #44:
score: 0
Accepted
time: 3ms
memory: 3760kb
input:
4 4 14.593389
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 0.9262241952 4.0000000000 4.0000000000
result:
ok correct
Test #45:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
2 2 4.0
output:
3 0.0000000000 0.0000000000 0.0000000000 1.9999999990 2.0000000000 2.0000000000
result:
ok correct
Test #46:
score: 0
Accepted
time: 2ms
memory: 3856kb
input:
3 3 5.0
output:
3 0.0000000000 0.0000000000 0.0000000000 1.7499999984 3.0000000000 3.0000000000
result:
ok correct
Test #47:
score: 0
Accepted
time: 2ms
memory: 3824kb
input:
4 4 15.123
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 2.7805560976 4.0000000000 4.0000000000
result:
ok correct
Test #48:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
4 4 14.1
output:
6 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 1.2404761882 0.0000000000 4.0000000000 4.0000000000
result:
ok correct
Test #49:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
3 3 9.0
output:
5 0.0000000000 0.0000000000 0.0000000000 3.0000000000 1.0000000000 3.0000000000 1.0000000000 0.9000000006 3.0000000000 3.0000000000
result:
ok correct
Test #50:
score: 0
Accepted
time: 2ms
memory: 3820kb
input:
4 4 16.0
output:
7 0.0000000000 0.0000000000 0.0000000000 4.0000000000 1.0000000000 4.0000000000 1.0000000000 0.0000000000 2.0000000000 0.0000000000 2.0000000000 3.9999999990 4.0000000000 4.0000000000
result:
ok correct