QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#83289 | #5612. Picking Up Steam | jeroenodb | WA | 2ms | 3532kb | C++17 | 9.3kb | 2023-03-01 11:19:19 | 2023-03-01 11:19:22 |
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),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'