QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#83290 | #5612. Picking Up Steam | jeroenodb | WA | 2ms | 3696kb | C++17 | 9.3kb | 2023-03-01 11:20:31 | 2023-03-01 11:20:32 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
typedef long double lld;
#define __int128_t lld
struct fraction {
__int128_t a=0,b=1;
fraction() {}
fraction(ll x) : a(x) {}
fraction(__int128_t a, __int128_t b) : a(a),b(b) {}
bool operator<(const fraction& o) const {return a*o.b < b*o.a;}
bool operator>(const fraction& o) const {return a*o.b > b*o.a;}
bool operator<=(const fraction& o) const {return a*o.b <= b*o.a;}
bool operator>=(const fraction& o) const {return a*o.b >= b*o.a;}
bool operator==(const fraction& o) const {return a*o.b == b*o.a;}
bool operator!=(const fraction& o) const {return a*o.b != b*o.a;}
friend fraction sqrt(const fraction& a) { // never use it!
return {-1,-1};
}
fraction operator-() const {
return {-a,b};
}
void simp() {
// auto g = gcd(a,b);
// if(g) {
// a/=g,b/=g;
// }
// if(max(a,b)>=__int128_t(4e18)) {
// while(max(a,b)>=__int128_t(4e18)) a/=2,b/=2;
// if(b==0) b=1;
// g = gcd(a,b);
// a/=g,b/=g;
// }
}
fraction simplify() const {
auto res = *this;
res.simp();
return res;
}
friend fraction abs(const fraction& a) {
if(a.a<0) return {-a.a,a.b};
return a;
}
fraction& operator+=(const fraction& o) {
a = a*o.b + b*o.a;
b*=o.b;
simp();
return *this;
}
fraction& operator-=(const fraction& o) {
a = a*o.b - b*o.a;
b*=o.b;
simp();
return *this;
}
fraction& operator*=(const fraction& o) {
a*=o.a;
b*=o.b;
simp();
return *this;
}
fraction& operator/=(const fraction& o) {
a*=o.b;
b*=o.a;
// assert(b!=0);
if(b<0) b=-b,a=-a;
simp();
return *this;
}
friend fraction operator+(fraction a, const fraction& b) { a+=b; return a; }
friend fraction operator-(fraction a, const fraction& b) { a-=b; return a; }
friend fraction operator*(fraction a, const fraction& b) { a*=b; return a; }
friend fraction operator/(fraction a, const fraction& b) { a/=b; return a; }
friend istream& operator>>(istream& in, fraction& a) {
ll c;
in >> c;
a.a=c;
return in;
}
friend ostream& operator<<(ostream& out, fraction& a) {
out << ll(a.a) << '/' << ll(a.b);
return out;
}
explicit operator double() {
return double(a)/double(b);
}
};
typedef fraction ld;
typedef complex<ld> pt;
#define X real()
#define Y imag()
auto cross(pt u, pt v) {return (ld)u.X*v.Y-(ld)u.Y*v.X;}
auto sgn(ld a) {return (a.a>0)-(a.a<0) ;}
bool isZero(pt p) {
return abs(p.X)+abs(p.Y)==0;
}
auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
auto in(pt p1, pt p2) {return (ld)p1.X*p2.X+(ld)p1.Y*p2.Y;}
auto norm(pt p) {return (ld)p.X*p.X+(ld)p.Y*p.Y;}
bool comp(const pt& a, const pt& b) { return a.Y>b.Y or (a.Y==b.Y and a.X < b.X);}
void read(pt& p) {
int a,b; cin >> a >> b;
p = {fraction(a),fraction(b)};
}
bool segseg(pt p, pt q, pt a, pt b) { // strict segment segment intersection
return sgn(ccw(p,q,a))*sgn(ccw(p,q,b))==-1 and sgn(ccw(a,b,p))*sgn(ccw(a,b,q))==-1;
}
bool onRay(pt p, pt dir, pt a) { // strictly on ray
if(sgn(ccw(p,p+dir,a))!=0) return false;
return in(a-p,dir)>=0;
}
bool onSegment(pt p, pt q, pt c) {
if(sgn(ccw(p,q,c))!=0) return false;
auto v = c-p;
auto tmp = in(v,q-p);
return fraction(0)<tmp and tmp<norm(q-p);
}
template<class P> pt lineInter(P s1, P e1, P s2, P e2) {
ld d = cross(e1 - s1,e2 - s2);
ld p = ccw(s2,e1, e2), q = ccw(s2,e2, s1);
return (s1 * p + e1 * q) / d;
}
ld segdist(pt l, pt r, pt a, pt b, pt dir) {
if(segseg(a,b,l,r)) {
return 0;
}
ld ans;
bool f=1;
for(int rep=0;rep<2;++rep) {
for(auto p : {l,r}) {
auto cur = min(norm(p-a),norm(p-b));
if(f==1) {
f=0;
ans=cur;
}
ans=min(ans,cur);
pt v = b-a, w = p-a;
if(in(v,w)>=0 and in(v,w)<=in(v,v)) {
if(rep==0) v=dir;
ans=min(ans,cross(v,w)*cross(v,w)/norm(v));
}
}
swap(l,a);
swap(r,b);
}
return ans;
}
ld segline(pt l, pt r, pt a, pt b) { // seg, line
if(sgn(ccw(a,b,l))*sgn(ccw(a,b,r))==-1) {
return 0;
}
ld ans;
bool f=1;
for(auto p : {l,r}) {
pt v = b-a, w = p-a;
auto cur = cross(v,w)*cross(v,w)/norm(v);
if(f==1) {
f=0;
ans=cur;
}
ans=min(ans,cur);
}
return ans;
}
int main() {
// intersection of circle and polygon = closest distance calculation + point in polygon
// use fractions?
// maybe becomes weird
// can use fractions of x/2000?
// yeah, that could be useful
// how big? pfooo, dat is moeilijk
// misschien toch python?
// just take fraction class
// then geometry and so on
// line inter is useful
// start met camera berekenen: lineinter
// dan links en rechts ga er overheen, als in gezichtsveld,
// cirkel + twee lijnen, checken of echt snijden
// een lijn: of gaat er helemaal doorheen, of zit er in.
// point in polygon
// of zit er strikt buiten --> geen enkele intersection.
// strict
// zijkanten "oneindig" hoog.
// oneinding = kwadratisch hoog
// segment distance
int n; cin >> n;
++n;
vector<pt> pts(n);
for(auto& p : pts) read(p);
int mid=-1;
{
int c;
cin >> c;
int i=0;
while(pts[i].X<c) ++i;
if(pts[i].X==c) {
mid=i;
} else {
pt ori = lineInter(pts[i-1],pts[i],pt{ld(c),ld(0)},pt{ld(c),ld(1)});
pts.insert(pts.begin()+i,ori);
mid=i;
}
if(ld(c)!=pts[0].X) pts.insert(pts.begin(),pts.front()+pt{ld(0),ld(5e3)}),++mid;
if(ld(c)!=pts.back().X) pts.push_back(pts.back()+pt{ld(0),ld(5e3)});
}
n = pts.size();
pt steams; read(steams);
int r; cin >> r;
pt steamdir; read(steamdir);
int v; cin >> v;
// ok en nu?
// maak die polygoon!
vector<pt> poly;
{
pt ori = pts[mid];
poly = {ori};
if(mid+1<n) {
pt dir = pts[mid+1]-ori;
for(int i=mid+1;i<n;++i) {
if(i==n-1 or ccw(ori,ori+dir,pts[i])>0) {
poly.push_back(lineInter(ori,ori+dir,pts[i-1],pts[i]));
if(i!=n-1) poly.push_back(pts[i]);
dir=pts[i]-ori;
}
}
}
if(mid) {
pt dir = pts[mid-1]-ori;
vector<pt> polyl;
for(int i=mid-1;i>=0;--i) {
if(i==0 or ccw(ori,ori+dir,pts[i])<0) {
polyl.push_back(lineInter(ori,ori+dir,pts[i],pts[i+1]));
if(i!=0) polyl.push_back(pts[i]);
dir=pts[i]-ori;
}
}
reverse(all(polyl));
poly.insert(poly.begin(),all(polyl));
}
}
n = poly.size();
// nu binary search?
// seconde*1000 1e8 steps?
double lo = 0.0005, hi = 1./v;
bool gd=0;
auto intersect = [&](double t) {
double len = t*v;
auto vlen = sqrtl(norm(steamdir).a);
len/= vlen;
// round to what?
// int prec = 1<<30;
double prec=1;
while(len<=1000 and prec<=1000) {
prec*=2;
len*=2;
}
ld flen = ld(llround(len),llround(prec)); // how precise?
pt s = steams;
pt e = s+ steamdir*flen;
ld dist2;
for(int i=0;i+1<n;++i) {
auto myd = segdist(poly[i],poly[i+1],s,e,steamdir);
if(i==0) {
dist2=myd;
} else dist2= min(dist2,myd);
}
if(dist2<ld(r*r)) return true;
return false;
};
bool bad=1;
for(int i=0;i+1<n;++i) {
auto myd = segline(poly[i],poly[i+1],steams,steams+steamdir);
if(myd<r*r) bad=0;
}
if(bad) {
cout << "-1\n";
exit(0);
}
while(!intersect(hi)) {
hi*=2;
}
for(int rep=0;rep<60;++rep) {
double mid = (lo+hi)/2;
if(intersect(mid)) {
gd=1;
hi = mid;
} else lo = mid;
}
if(gd) {
cout << setprecision(15) << (lo+hi)*0.5 << '\n';
} else cout << "-1\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3484kb
input:
7 1 0 2 2 4 2 5 5 6 0 9 4 12 3 14 0 2 13 -1 1 -1 1 1
output:
8.89683961797605
result:
ok found '8.89684', expected '8.89900', error '0.00024'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
3 0 0 3 3 6 3 9 0 3 4 1 1 -1 1 1
output:
1.12073662682204
result:
ok found '1.12074', expected '1.12132', error '0.00052'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
3 0 0 3 3 6 3 9 0 4 4 1 1 -1 1 1
output:
1.4149040963391
result:
ok found '1.41490', expected '1.41421', error '0.00049'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
3 0 0 3 3 6 3 9 0 4 4 1 1 1 1 1
output:
1.4149040963391
result:
ok found '1.41490', expected '1.41421', error '0.00049'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
3 0 0 3 3 6 3 9 0 8 4 1 1 1 1 1
output:
1.82784340800859
result:
ok found '1.82784', expected '1.82843', error '0.00032'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 0 0 3 3 6 3 9 0 0 4 1 1 0 1 1
output:
1.58544921875
result:
ok found '1.58545', expected '1.58579', error '0.00021'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3372kb
input:
3 0 0 3 3 6 3 9 0 0 4 1 1 1 1 1
output:
-1
result:
ok found '-1.00000', expected '-1.00000', error '-0.00000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
2 10 10 30 40 60 60 50 40 30 10 -1 1 1
output:
3.94294894587421
result:
ok found '3.94295', expected '3.94410', error '0.00029'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
5 0 80 40 0 60 60 100 0 120 40 160 60 0 140 20 20 -1 1 1
output:
7.20088819747394
result:
ok found '7.20089', expected '7.20242', error '0.00021'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
5 0 80 40 0 60 60 100 0 120 40 160 60 0 140 20 20 0 1 1
output:
7.638671875
result:
ok found '7.63867', expected '7.63932', error '0.00008'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3672kb
input:
3 -4 4 -1 3 0 0 3 3 -4 2 0 1 -1 1 1
output:
2.00600117123723
result:
ok found '2.00600', expected '2.00657', error '0.00028'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
9 -12 5 -10 2 -8 7 -6 5 -5 2 -3 2 -2 3 -1 6 1 6 3 4 0 -8 3 1 1 1 1
output:
2.8298081926782
result:
ok found '2.82981', expected '2.82843', error '0.00049'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
9 -12 5 -10 2 -8 7 -6 5 -5 2 -3 2 -2 3 -1 6 1 6 3 4 -12 -8 3 1 1 1 1
output:
8.15106293469336
result:
ok found '8.15106', expected '8.15143', error '0.00005'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
8 -4956 0 -413 0 413 1239 1239 0 1652 826 2478 826 3404 1239 3717 1239 5000 0 413 -1239 -1652 413 2 1 1
output:
2771.60625811099
result:
ok found '2771.60626', expected '2770.48822', error '0.00040'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
2 0 3 3 0 6 3 1 3 -1 1 0 1 1
output:
0.0005
result:
ok found '0.00050', expected '0.00000', error '0.00050'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
20 1 11 4 1 5 14 6 8 8 8 9 1 12 14 14 12 17 8 21 6 25 1 27 8 29 4 35 5 37 16 38 17 39 16 45 9 47 4 48 11 49 2 6 21 -2 1 0 15 5
output:
4.71826171875
result:
ok found '4.71826', expected '4.71716', error '0.00023'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
20 2 10 4 4 6 13 9 3 10 12 11 5 12 0 14 15 15 10 17 20 19 8 21 4 28 18 29 7 32 10 36 2 39 0 40 5 41 6 42 18 47 2 33 34 -11 4 -3 13 1
output:
15.3546397456766
result:
ok found '15.35464', expected '15.35383', error '0.00005'
Test #18:
score: -100
Wrong Answer
time: 2ms
memory: 3540kb
input:
33 -4858 1505 -4750 252 -4377 2301 -4299 1512 -4124 4848 -3928 551 -3650 1782 -3242 163 -3241 4713 -2817 1286 -2753 2708 -1859 4013 -991 2481 -837 2253 356 669 385 4947 558 336 841 4286 1041 91 1122 3030 1371 4183 1456 1266 1632 844 1802 4762 2340 4087 2353 2421 2696 1915 3294 220 4405 3012 4413 481...
output:
0.0005
result:
wrong answer 1st numbers differ - expected: '43.61806', found: '0.00050', error = '0.99999'