QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#393796 | #5612. Picking Up Steam | Jose_17 | WA | 1ms | 4064kb | C++20 | 10.0kb | 2024-04-19 12:36:16 | 2024-04-19 12:36:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
// Holi c:
#define ll long long int
//#define ld long double
#define ii __int128
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
const int Inf = 1e7;
const ll mod = 998244353;
const ll INF = 1e18;
const int maxn = 3e5 + 5;
using ld = long double;
const ld eps = 1e-9, inf = numeric_limits<ld>::max(), pi = acos(-1);
// For use with integers, just set eps=0 and everything remains the same
bool geq(ld a, ld b){return a-b >= -eps;} //a >= b
bool leq(ld a, ld b){return b-a >= -eps;} //a <= b
bool ge(ld a, ld b){return a-b > eps;} //a > b
bool le(ld a, ld b){return b-a > eps;} //a < b
bool eq(ld a, ld b){return abs(a-b) <= eps;} //a == b
bool neq(ld a, ld b){return abs(a-b) > eps;} //a != b
struct point{
ld x, y;
point(): x(0), y(0){}
point(ld x, ld y): x(x), y(y){}
point operator+(const point & p) const{return point(x + p.x, y + p.y);}
point operator-(const point & p) const{return point(x - p.x, y - p.y);}
point operator*(const ld & k) const{return point(x * k, y * k);}
point operator/(const ld & k) const{return point(x / k, y / k);}
point operator+=(const point & p){*this = *this + p; return *this;}
point operator-=(const point & p){*this = *this - p; return *this;}
point operator*=(const ld & p){*this = *this * p; return *this;}
point operator/=(const ld & p){*this = *this / p; return *this;}
point rotate(const ld & a) const{return point(x*cos(a) - y*sin(a), x*sin(a) + y*cos(a));}
point perp() const{return point(-y, x);}
ld ang() const{
ld a = atan2l(y, x); a += le(a, 0) ? 2*pi : 0; return a;
}
ld dot(const point & p) const{return x * p.x + y * p.y;}
ld cross(const point & p) const{return x * p.y - y * p.x;}
ld norm() const{return x * x + y * y;}
ld length() const{return sqrtl(x * x + y * y);}
point unit() const{return (*this) / length();}
bool operator==(const point & p) const{return eq(x, p.x) && eq(y, p.y);}
bool operator!=(const point & p) const{return !(*this == p);}
bool operator<(const point & p) const{return le(x, p.x) || (eq(x, p.x) && le(y, p.y));}
bool operator>(const point & p) const{return ge(x, p.x) || (eq(x, p.x) && ge(y, p.y));}
bool half(const point & p) const{return le(p.cross(*this), 0) || (eq(p.cross(*this), 0) && le(p.dot(*this), 0));}
};
istream &operator>>(istream &is, point & p){return is >> p.x >> p.y;}
ostream &operator<<(ostream &os, const point & p){return os << "(" << p.x << ", " << p.y << ")";}
int sgn(ld x){
if(ge(x, 0)) return 1;
if(le(x, 0)) return -1;
return 0;
}
bool pointInLine(const point & a, const point & v, const point & p){
//line a+tv, point p
return eq((p - a).cross(v), 0);
}
bool pointInSegment(const point & a, const point & b, const point & p){
//segment ab, point p
return pointInLine(a, b - a, p) && leq((a - p).dot(b - p), 0);
}
point intersectLines(const point & a1, const point & v1, const point & a2, const point & v2){
//lines a1+tv1, a2+tv2
//assuming that they intersect
ld det = v1.cross(v2);
return a1 + v1 * ((a2 - a1).cross(v2) / det);
}
int intersectLinesInfo(const point & a1, const point & v1, const point & a2, const point & v2){
//lines a1+tv1 and a2+tv2
ld det = v1.cross(v2);
if(eq(det, 0)){
if(eq((a2 - a1).cross(v1), 0)){
return -1; //infinity points
}else{
return 0; //no points
}
}else{
return 1; //single point
}
}
int intersectLineSegmentInfo(const point & a, const point & v, const point & c, const point & d){
//line a+tv, segment cd
point v2 = d - c;
ld det = v.cross(v2);
if(eq(det, 0)){
if(eq((c - a).cross(v), 0)){
return -1; //infinity points
}else{
return 0; //no point
}
}else{
return sgn(v.cross(c - a)) != sgn(v.cross(d - a)); //1: single point, 0: no point
}
}
int intersectSegmentsInfo(const point & a, const point & b, const point & c, const point & d){
//segment ab, segment cd
point v1 = b - a, v2 = d - c;
int t = sgn(v1.cross(c - a)), u = sgn(v1.cross(d - a));
if(t == u){
if(t == 0){
if(pointInSegment(a, b, c) || pointInSegment(a, b, d) || pointInSegment(c, d, a) || pointInSegment(c, d, b)){
return -1; //infinity points
}else{
return 0; //no point
}
}else{
return 0; //no point
}
}else{
return sgn(v2.cross(a - c)) != sgn(v2.cross(b - c)); //1: single point, 0: no point
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
int n; cin>>n; vector<point> v(n + 1);
for(int i = 0; i <= n; i++){
int a, b; cin>>a>>b; v[i] = point(a, b);
}
int cx, sx, sy, r, dx, dy, v1; cin>>cx>>sx>>sy>>r>>dx>>dy>>v1;
point ini(sx, sy); point vt(dx, dy); vt = vt.unit() * v1; point cam;
for(int i = 0; i < n; i++){
if(cx >= v[i].x && cx <= v[i + 1].x){
cam = intersectLines(v[i], v[i + 1] - v[i], point(cx, 0), point(cx, Inf) - point(cx, 0));
break;
}
}
cam.x = cx;
//cout<<"Camara en: "<<cam<<" Punto inicial en: "<<ini<<" Con vector: "<<vt<<'\n';
//cout<<"Poli-linea : "; for(auto e : v) cout<<e<<" "; cout<<'\n';
vector<point> side1, side2, izq, der;
int j1 = 0; //izq.pb(v[0]);
while(v[j1].x < cam.x) izq.pb(v[j1++]);
if(v[j1] == cam) j1++;
while(j1 <= n) der.pb(v[j1++]);
int m = izq.size(), k = der.size();
//cout<<"Izq"<<'\n'; for(auto e : izq) cout<<e<<" "; cout<<'\n';
//cout<<"Der"<<'\n'; for(auto e : der) cout<<e<<" "; cout<<'\n';
//Reconstuir el poligono en dos partes segun quienes p0.x < cam.x || p0.x > cam.x
//Introducir todos aquellos puntos (puntos limites de la poli-linea e intersecciones de la linea de vision con los segmentos) que se puedan ver desde cam
//side1
for(int i = 0; i < k; i++){
side1.pb(der[i]);
for(int j = 0; j < k - 1; j++){
if(intersectLineSegmentInfo(cam, der[i] - cam, der[j], der[j + 1]) == 1){
auto it = intersectLines(cam, der[i] - cam, der[j], der[j + 1] - der[j]);
if(it != der[i] && it != der[i + 1]) side1.pb(it);
}
}
} //der.pb(der[der.size() - 1]);
sort(all(side1));
//side2
for(int i = 0; i < m; i++){
side2.pb(izq[i]);
for(int j = 0; j < m - 1; j++){
if(intersectLineSegmentInfo(cam, izq[i] - cam, izq[j], izq[j + 1]) == 1){
auto it = intersectLines(cam, izq[i] - cam, izq[j], izq[j + 1] - izq[j]);
if(it != izq[j] && it != izq[j + 1]) side2.pb(it);
}
}
}
sort(all(side2)); reverse(all(side2)); reverse(all(izq));
//side1.erase(unique(all(side1)), side1.end()); side2.erase(unique(all(side2)), side2.end());
//cout<<"Side1"<<'\n'; for(auto e : side1) cout<<e<<" "; cout<<'\n';
//cout<<"Side2"<<'\n'; for(auto e : side2) cout<<e<<" "; cout<<'\n';
//Limpiar los puntos, dado la anterior linea de vision mas proxima, verificar si se puede ver el punto
vector<point> polyd, polyi;
int j = 0, a = 1;
for(int i = 0; i < side1.size(); i++){
if(j + a < k){
if(side1[i] == der[j + a]){
if((der[j] - cam).cross(side1[i] - cam) > eps) j += a, a = 1;
else a++;
}
}
if((der[j] - cam).cross(side1[i] - cam) >= -eps) polyd.pb(side1[i]);
//cout<<"Punto a analizar: "<<side1[i]<<" Con linea de vision en: "<<der[j]<<'\n';
}
j = 0; a= 1;
for(int i = 0; i < side2.size(); i++){
if(j + a < m){
if(side2[i] == izq[j + a]){
if((izq[j] - cam).cross(side2[i] - cam) < -eps) j += a, a = 1;
else a++;
}
}
if((izq[j] - cam).cross(side2[i] - cam) <= eps) polyi.pb(side2[i]);
}
//Añadimos un punto final para representar el infinito
if(polyd.size()) polyd.pb(cam + (polyd[polyd.size() - 1] - cam) * Inf);
if(polyi.size()) polyi.pb(cam + (polyi[polyi.size() - 1] - cam) * Inf);
//cout<<"Polyd"<<'\n'; for(auto e : polyd) cout<<e<<" "; cout<<'\n';
//cout<<"Polyi"<<'\n'; for(auto e : polyi) cout<<e<<" "; cout<<'\n';
//Verificar el tiempo que tarda la nube en cbocar con algun segmento del poliogno
//Formula o ternaria
ld ans = INF;
for(int i = 0; i < polyd.size(); i++){
point p0, p1 = polyd[i];
if(i) p0 = polyd[i - 1]; else p0 = cam;
if(p0 == p1) continue;
if(abs((p0 - p1).cross(vt)) <= eps){
if(abs((p0 - ini).cross(p1 - ini)) <= eps) ans = min(ans, min((abs(p0.y - ini.y) - r) / vt.y, (abs(p1.y - ini.y) - r) / vt.y));
}else{
point bi = p1 - p0; bi = bi.perp();
auto at = intersectLines(ini, bi, p0, p1 - p0);
if(at.x + eps < min(p0.x, p1.x) || at.x - eps > max(p0.x, p1.x)){
if((ini - p0).length() < (ini - p1).length()) at = p0; else at = p1;
}
point nw = ini + (at - ini).unit() * r;
auto it = intersectLines(nw, vt, p0, p1 - p0);
if(it.x - eps < min(p0.x, p1.x) || it.x - eps > max(p0.x, p1.x)) continue;
ld ny = (it.y - nw.y) / vt.y;
if(ny >= -eps) ans = min(ans, ny);
}
}
for(int i = 0; i < polyi.size(); i++){
point p0, p1 = polyi[i];
if(i) p0 = polyi[i - 1]; else p0 = cam;
if(p0 == p1) continue;
if(abs((p0 - p1).cross(vt)) <= eps){
if(abs((p0 - ini).cross(p1 - ini)) <= eps) ans = min(ans, min((abs(p0.y - ini.y) - r) / vt.y, (abs(p1.y - ini.y) - r) / vt.y));
}else{
point bi = p1 - p0; bi = bi.perp();
auto at = intersectLines(ini, bi, p0, p1 - p0);
if(at.x + eps < min(p0.x, p1.x) || at.x - eps > max(p0.x, p1.x)){
if((ini - p0).length() < (ini - p1).length()) at = p0; else at = p1;
}
point nw = ini + (at - ini).unit() * r;
auto it = intersectLines(nw, vt, p0, p1 - p0);
if(it.x - eps < min(p0.x, p1.x) || it.x - eps > max(p0.x, p1.x)) continue;
ld ny = (it.y - nw.y) / vt.y;
if(ny >= -eps) ans = min(ans, ny);
}
}
if(ans == INF) cout<<-1;
else cout<<setprecision(25)<<ans;
}
// https://codeforces.com/gym/104614/problem/H
/*
11
1 10
2 6
4 5
5 3
6 2
9 2
12 3
13 3
15 5
16 8
17 8
18 6
7
7 -100
1
1 1
1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4064kb
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.899494936611665341780197
result:
ok found '8.89949', expected '8.89900', error '0.00006'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
3 0 0 3 3 6 3 9 0 3 4 1 1 -1 1 1
output:
1.121320343559642573145682
result:
ok found '1.12132', expected '1.12132', error '0.00000'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3860kb
input:
3 0 0 3 3 6 3 9 0 4 4 1 1 -1 1 1
output:
1.563516060678838364697216
result:
wrong answer 1st numbers differ - expected: '1.41421', found: '1.56352', error = '0.10557'