QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#744250#8985. Bikes and BarricadesrahulmnavneethAC ✓1ms3992kbC++175.9kb2024-11-13 21:19:132024-11-13 21:19:17

Judging History

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

  • [2024-11-13 21:19:17]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3992kb
  • [2024-11-13 21:19:13]
  • 提交

answer

/*
        File: icpc-mock-131124-E-B_main.cpp
        Date and Time Created: 2024-11-13 18:24:28
        Author: Rahul M. Navneeth
*/

/* ----------------- HEADER FILES ----------------- */

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* ----------------- NAMESPACE ----------------- */

using namespace std;
using namespace chrono;
using namespace __gnu_pbds;

/* ----------------- TEMPLATES ------------------ */

/* clang-format off */

// MACROS
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define io freopen("./input.txt", "r", stdin); freopen("./output.txt", "w", stdout); freopen("./output.txt", "w", stderr);

// TYPEDEF
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; // POLICY BASED DS

// SHORTCUTS
#define ar array
#define pb push_back
#define pob pop_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second
#define UNIQUE_SORT(v) sort(all(v)); v.erase(unique(all(v)), v.end())

// FUNCTIONS
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void swap(int &x, int &y) { int temp = x; x = y; y = temp; }
ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) { ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m; }
bool revsort(ll a, ll b) {return a > b;}
ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))
ll getRandomNumber(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} 
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll modpow(ll a, ll b, ll MOD) { ll res = 1; while(b > 0) { if(b & 1) { res = (res * a) % MOD; } b = b >> 1; a = (a*a) % MOD; } return res; }
void extendgcd(ll a, ll b, ll *v) { if (b == 0) { v[0] = 1; v[1] = 0; v[2] = a; return; }
extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return; } // PASS AN ARRY OF SIZE1 3
ll mminv(ll a, ll b) { ll arr[3]; extendgcd(a, b, arr); return arr[0]; } // FOR NON PRIME B
ll mminvprime(ll a, ll b) { return modpow(a, b - 2, b); }
ll mod_add(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a + b) % m) + m) % m; }
ll mod_mul(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a * b) % m) + m) % m; }
ll mod_sub(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a - b) % m) + m) % m; }
ll mod_div(ll a, ll b, ll m) { a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m; } // ONLY FOR PRIME M
void precision(int a) { cout << setprecision(a) << fixed; }

// CONSTANTS
const float PI = 3.141592653589793238462;
const int MOD = 1e9 + 7;
const int mxn = 1e7;
const int LOG = 30;

/* --------------------- CODE BEGINS ---------------------- */

struct point2d {
    double x, y;
    point2d() {}
    point2d(double x, double y): x(x), y(y) {}
    point2d& operator+=(const point2d &t) {
        x += t.x;
        y += t.y;
        return *this;
    }
    point2d& operator-=(const point2d &t) {
        x -= t.x;
        y -= t.y;
        return *this;
    }
    point2d& operator*=(double t) {
        x *= t;
        y *= t;
        return *this;
    }
    point2d& operator/=(double t) {
        x /= t;
        y /= t;
        return *this;
    }
    point2d operator+(const point2d &t) const {
        return point2d(*this) += t;
    }
    point2d operator-(const point2d &t) const {
        return point2d(*this) -= t;
    }
    point2d operator*(double t) const {
        return point2d(*this) *= t;
    }
    point2d operator/(double t) const {
        return point2d(*this) /= t;
    }
};

point2d operator*(double a, point2d b) {
    return b * a;
}

void solve() {
    ll N; cin >> N;
    ar<point2d, 2> a[N];
    for (ll i = 0; i < N; i++) cin >> a[i][0].x >> a[i][0].y >> a[i][1].x >> a[i][1].y;
    
    double mn = numeric_limits<double>::infinity();
    bool b = 0;

    for (ll i = 0; i < N; i++) {
        point2d p1 = a[i][0], p2 = a[i][1];
        
        if (p1.x * p2.x < 0) {
            double y_intersection = p1.y + (p2.y - p1.y) * (-p1.x) / (p2.x - p1.x);
            if (y_intersection > 0) {
                double d = y_intersection;
                if (d < mn) {
                    mn = d;
                    b = 1;
                }
            }
        } else if (p1.x == 0 && p1.y > 0) {
            double d = p1.y;
            if (d < mn) {
                mn = d;
                b = 1;
            }
        } else if (p2.x == 0 && p2.y > 0) {
            double d = p2.y;
            if (d < mn) {
                mn = d;
                b = true;
            }
        }
    }
    
    if (b) {
		precision(10);
		cout << mn << "\n";
    } else {
		cout << -1.0 << "\n";
    }
}

/*---------------------- MAIN DRIVER ------------------------*/

// MAIN
int32_t main() {
  fast_io
  #ifndef ONLINE_JUDGE
    io;
  #endif
  high_resolution_clock::time_point start, end;
  #ifndef ONLINE_JUDGE
    start = chrono::high_resolution_clock::now();
  #endif
  int t = 1;
  int i = 1;
  // cin >> t;
  while (i <= t) {
  	#ifndef ONLINE_JUDGE
		cout << "TESTCASE #" << i << "\n";
	#endif
	i++;
    solve();
  }
  #ifndef ONLINE_JUDGE
    end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
    cout << "-------------\nRUNTIME: " << duration.count() << " ms\n";
  #endif
  return 0;
}

/* clang-format on */

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3860kb

input:

2
-10 7 5 19
-1 -1 8 21

output:

1.4444444444

result:

ok found '1.44444', expected '1.44444', error '0.00000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

2
4 -6 -12 -1
3 5 8 8

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

1
1 -2 1 3

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

1
10 19 -20 19

output:

19.0000000000

result:

ok found '19.00000', expected '19.00000', error '0.00000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

1000
2 -30 46 25
59 15 78 -78
49 -74 9 35
-45 -34 55 -18
-81 -66 -79 -85
63 -9 99 27
64 94 29 -29
-40 -41 -39 -33
-92 0 -83 -80
-100 64 -2 68
97 -93 57 -31
87 99 -44 -91
-20 -50 68 24
73 -78 37 96
-57 -38 28 -82
-83 46 -66 -8
11 -18 21 72
-82 -7 -11 9
26 -62 45 45
31 13 24 33
35 11 98 -42
57 -23 69 ...

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

1000
36 -21 1 -27
16 -90 -22 -36
54 -69 58 -52
62 15 91 -90
-50 -91 -74 -7
75 -68 -18 -50
-50 67 -72 -58
39 -18 -67 -70
48 -67 -88 73
45 89 67 28
-60 -36 75 21
-83 -20 97 -14
-87 -91 -4 11
-45 -48 -21 -8
-32 25 -45 -78
-91 90 -47 -1
-68 -61 6 -84
-27 17 -58 9
46 -76 -16 -24
74 48 91 87
45 -66 -67 21...

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3912kb

input:

1000
-67 13 28 -24
-50 -93 -5 44
35 -27 -14 0
39 -8 -100 -19
-25 -86 47 3
-38 29 -43 50
60 -44 96 -61
13 79 73 -28
44 29 8 52
60 -51 3 5
-75 85 4 -87
91 8 32 -38
19 -63 52 -81
-56 -85 57 49
19 49 28 29
-38 -87 50 22
-34 -11 2 -46
96 -9 42 -26
-80 85 -12 96
60 85 54 54
81 -99 35 -39
-80 -27 -15 59
-1...

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3968kb

input:

1000
-96 67 9 -80
-97 -50 16 -46
-7 -77 -73 18
-19 -33 84 -18
15 -65 46 32
-32 85 -87 -53
-99 -84 -73 -48
34 -92 12 6
94 51 -10 -32
43 0 -18 -60
68 -69 -42 18
-42 22 67 -89
-24 41 -4 -11
-21 -71 37 -3
-12 97 -9 59
-10 -28 -70 4
-70 9 -36 26
-80 -35 97 -2
-77 -49 -9 -82
13 -41 -34 93
9 -80 53 71
12 -...

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3944kb

input:

1000
-92 -84 -38 88
-13 -72 -25 -82
48 49 -30 -69
7 -95 21 -91
79 72 94 65
10 94 4 -37
-69 -81 93 -65
23 54 63 60
34 89 43 78
-100 81 -15 0
47 -71 -91 85
-87 39 41 -30
-57 -57 63 37
-58 13 -98 -10
-8 82 -87 -89
47 -70 92 -10
53 -69 80 -60
12 57 74 39
-99 -61 87 -9
-43 19 -59 -60
99 -11 86 -61
24 -30...

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

1000
-52 47 -45 -81
-38 -73 -58 -100
68 -35 8 36
-86 53 22 76
30 -71 -44 -52
31 -95 64 -5
58 -47 37 38
-40 -29 -57 76
-56 -40 84 93
-37 26 16 -15
-18 34 -45 -44
-38 -19 -58 -25
55 41 -87 -97
80 -55 23 11
-75 -12 31 -47
51 36 -19 -7
40 59 7 -85
83 -59 65 -1
-86 -85 -26 -87
79 83 32 -23
79 68 -85 54
-...

output:

0.3488372093

result:

ok found '0.34884', expected '0.34884', error '0.00000'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3992kb

input:

1000
55 57 -86 -37
83 81 2 10
4 15 26 94
-75 13 58 -76
-61 15 89 65
34 -31 -78 4
74 -50 -3 75
-100 -54 -21 -20
32 29 -42 -63
77 8 -65 -65
-11 -59 -93 43
-12 -49 -54 62
-61 11 17 -96
31 5 84 49
-59 -98 71 -96
3 -30 -42 -49
74 8 -78 91
36 55 -26 36
80 52 25 10
86 13 23 81
-3 77 77 27
-32 60 61 -51
-89...

output:

0.3894736842

result:

ok found '0.38947', expected '0.38947', error '0.00000'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3912kb

input:

1000
-8 -32 85 53
-43 -33 -56 -29
53 21 29 -73
-82 68 -81 -44
86 -25 23 5
18 -97 -69 -35
52 79 -44 99
76 76 5 22
-17 37 25 -48
89 -59 -44 -63
-90 71 -64 46
64 -88 -57 -97
-66 -48 46 21
-61 83 94 -65
-16 -71 78 81
-55 71 38 89
-61 -89 -37 -8
32 -18 69 -65
-98 -26 11 -50
53 -92 -77 47
46 51 -87 0
35 -...

output:

0.1654135338

result:

ok found '0.16541', expected '0.16541', error '0.00000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3968kb

input:

1000
24 -71 -17 0
-32 15 68 95
74 -49 46 8
84 83 83 31
-52 44 77 -92
-29 -17 -93 -44
79 9 -34 41
25 61 73 28
22 44 47 -94
8 81 -70 10
93 -6 76 41
76 73 -31 -50
31 -51 68 -60
-77 5 6 82
36 -17 83 -36
-24 -2 -58 85
9 -76 -89 70
-2 -85 -26 -88
-65 -9 88 98
-84 24 58 7
-47 -43 -23 54
-85 24 -83 -4
12 -9...

output:

0.5000000000

result:

ok found '0.50000', expected '0.50000', error '0.00000'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

1000
-18 1 11 77
-80 -53 -22 95
16 -3 -39 78
87 -85 54 -6
-55 13 -85 -38
82 -85 -5 -37
-36 -46 88 10
19 10 75 -60
48 27 -67 -37
-64 -61 78 -40
70 61 91 19
-43 51 86 52
-38 1 76 -41
23 67 -32 -94
39 -65 67 -84
-69 87 -37 6
-45 74 -98 60
27 -17 51 -9
-63 85 -53 -34
74 25 11 -81
96 -36 -58 -11
-27 -95 ...

output:

0.2869565217

result:

ok found '0.28696', expected '0.28696', error '0.00000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

10
-28 97 74 97
47 100 76 95
63 99 84 98
-34 98 11 99
-48 93 16 91
54 100 85 91
-80 97 27 95
-90 94 82 96
66 100 -74 91
-18 92 37 100

output:

91.5000000000

result:

ok found '91.50000', expected '91.50000', error '0.00000'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

10
57 94 75 100
15 95 26 96
34 98 -60 97
-37 99 -92 99
2 92 -63 98
22 91 -73 97
-83 91 -90 94
-19 90 -12 100
-26 97 -23 91
99 90 -38 95

output:

92.1846153846

result:

ok found '92.18462', expected '92.18462', error '0.00000'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

10
11 97 -85 94
53 95 -18 93
63 95 31 99
71 100 -37 94
-28 92 -68 100
71 92 -97 95
97 96 72 94
34 97 -75 91
27 91 92 96
-39 99 17 100

output:

93.2678571429

result:

ok found '93.26786', expected '93.26786', error '0.00000'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

10
68 93 -37 90
-43 96 29 99
-75 91 19 90
87 93 -11 92
-12 100 90 98
58 93 25 97
45 96 -94 92
-18 100 -4 98
-98 93 -37 94
92 94 -54 90

output:

90.2021276596

result:

ok found '90.20213', expected '90.20213', error '0.00000'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

10
-100 96 25 91
-91 94 -36 92
-17 94 52 100
4 97 -68 91
59 96 -41 98
-49 90 -4 94
91 97 -63 94
-84 98 24 94
41 100 -41 98
6 100 -30 93

output:

92.0000000000

result:

ok found '92.00000', expected '92.00000', error '0.00000'