QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#83289#5612. Picking Up SteamjeroenodbWA 2ms3532kbC++179.3kb2023-03-01 11:19:192023-03-01 11:19:22

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:19:22]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3532kb
  • [2023-03-01 11:19:19]
  • 提交

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),1); // 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: 0
Wrong Answer
time: 2ms
memory: 3532kb

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:

0.00897694155803234

result:

wrong answer 1st numbers differ - expected: '8.89900', found: '0.00898', error = '0.99899'