QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#83290#5612. Picking Up SteamjeroenodbWA 2ms3696kbC++179.3kb2023-03-01 11:20:312023-03-01 11:20:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-01 11:20:32]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3696kb
  • [2023-03-01 11:20:31]
  • 提交

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'