QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133875#6263. Keep Him InsideKhNURE_KIVI#AC ✓1ms3852kbC++147.8kb2023-08-02 16:17:042023-08-02 16:17:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 16:17:06]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3852kb
  • [2023-08-02 16:17:04]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

const int max_n = -1, inf = 1000111222;


struct point {
    ld x, y;
    int id;
};

inline bool cmp (point a, point b) {
    return a.x < b.x || a.x == b.x && a.y < b.y;
}

inline bool cw (point a, point b, point c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}

inline bool ccw (point a, point b, point c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}

void convex_hull (vector<point> & a) {
    if (len(a) <= 1) {
        return;
    }
    sort (a.begin(), a.end(), cmp);
    point p1 = a[0],  p2 = a.back();
    vector<point> up = {p1}, down = {p1};
    for (int i = 1; i < len(a); i++) {
        if (i == len(a) - 1 || cw (p1, a[i], p2)) {
            while (len(up) >= 2 && !cw(up[len(up) - 2], up.back(), a[i])) {
                up.pop_back();
            }
            up.pb(a[i]);
        }
        if (i == len(a) - 1 || ccw (p1, a[i], p2)) {
            while (len(down) >= 2 && !ccw(down[len(down) - 2], down.back(), a[i])) {
                down.pop_back();
            }
            down.pb(a[i]);
        }
    }
    a = up;
    for (int i = len(down) - 2; i > 0; i--) {
        a.pb(down[i]);
    }
}



struct line {
    /// ax + by + c = 0
    ld a, b, c;
    line () : a(0), b(0), c(0) {}

    line (ld a, ld b, ld c) : a(a), b(b), c(c) {}

    line (ld k, ld b) : a(-k), b(1), c(-b) {} /// y = kx + b

    line (point &a, point &b) : a(a.y - b.y), b(b.x - a.x), c(-a.y * (b.x - a.x) + a.x * (b.y - a.y)) {}

    void normalize () {
        if (c > 0) {
            c *= -1;
            a *= -1;
            b *= -1;
        }
        ld z = sqrt(a * a + b * b);
        a /= z;
        b /= z;
        c /= z;
    }

};



namespace math {

    inline ld det (ld a, ld b, ld c, ld d) {
        return a * d - b * c;
    }

    inline pair<ld, ld> solve (ld xa1, ld ya1, ld c1, ld xa2, ld ya2, ld c2) {
        ld d = det(xa1, ya1, xa2, ya2);
//    debug(xa1, ya1, c1, xa2, ya2, c2);
        if (d == 0) {
            return {-1, -1};
        }
        ld x = det(c1, ya1, c2, ya2);
        ld y = det(xa1, c1, xa2, c2);
        return {x / d, y / d};
    }

}

const ld eps = 1e-9;

inline int area (point a, point b, point c) {
    return abs(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
}

inline bool inside (int x, int y, point a, point b, point c) {
    point p{(ld)x, (ld)y, 0};
    int cur = area(a, b, c);
    int a1 = area(a, b, p);
    int a2 = area(a, c, p);
    int a3 = area(b, c, p);
    return cur == a1 + a2 + a3;
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int x, y;
    cin >> x >> y;
    vector <point> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i].x = x;
        a[i].y = y;
        a[i].id = i;
    }
    convex_hull(a);
    if (len(a) == 1) {
        if (a[0].x == x && a[0].y == y) {
            for (int i = 0; i < n; i++) {
                if (i == a[0].id) {
                    cout << "1\n";
                }
                else {
                    cout << "0\n";
                }
            }
        }
        else {
        }
        return 0;
    }
    int m = len(a);
    for (int i = 0; i < m; i++) {
        if (a[i].x == x && a[i].y == y) {
            for (int j = 0; j < n; j++) {
                if (j == a[i].id) {
                    cout << "1\n";
                }
                else {
                    cout << "0\n";
                }
            }
            return 0;
        }
    }
    cout << fixed;
    cout.precision(15);
    auto find_p = [] (point a, point b, ld x, ld y) {
        ld p = -1;
        if (a.x == b.x) {
            p = (ld)(y - b.y) / (a.y - b.y);
            if (abs(x - a.x) > eps) {
                p = -1;
            }
        }
        else if (a.y == b.y) {
            p = (ld)(x - b.x) / (a.x - b.x);
            if (abs(y - a.y) > eps) {
                p = -1;
            }
        }
        else {
            p = (ld)(y - b.y) / (a.y - b.y);
            ld p1 = (ld)(x - b.x) / (a.x - b.x);
            if (abs(p - p1) > eps) {
                p = -1;
            }
        }
        return p;
    };
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            if (a[i].x == a[j].x && a[i].y == a[j].y) {
                continue;
            }
            ld p = find_p(a[i], a[j], x, y);
            if (p < 0 || p > 1) {
                continue;
            }
            for (int k = 0; k < n; k++) {
                if (k == a[i].id) {
                    cout << p << '\n';
                }
                else if (k == a[j].id) {
                    cout << 1 - p << '\n';
                }
                else {
                    cout << "0\n";
                }
            }
            return 0;
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            for (int k = j + 1; k < m; k++) {
                if (inside(x, y, a[i], a[j], a[k])) {
                    point p{(ld)x, (ld)y, 0};
                    line l1(a[i], a[j]);
                    line l2(a[k], p);
                    auto gg = math::solve(l1.a, l1.b, -l1.c, l2.a, l2.b, -l2.c);
                    ld p1 = find_p(a[i], a[j], gg.first, gg.second);
                    ld p2 = find_p(a[k], point{gg.first, gg.second, 0}, x, y);
                    for (int i1 = 0; i1 < n; i1++) {
                        if (i1 == a[i].id) {
                            cout << p1 * (1 - p2) << '\n';
                        }
                        else if (i1 == a[j].id) {
                            cout << (1 - p1) * (1 - p2) << '\n';
                        }
                        else if (i1 == a[k].id) {
                            cout << p2 << '\n';
                        }
                        else {
                            cout << "0\n";
                        }
                    }
                    return 0;
                }
            }
        }
    }
    assert(false);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3852kb

input:

3 0 0
0 1
-10000 -1
10000 -1

output:

0.500000000000000
0.250000000000000
0.250000000000000

result:

ok correct

Test #2:

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

input:

3 1 1
0 0
3 0
0 3

output:

0.333333333333333
0.333333333333333
0.333333333333333

result:

ok correct

Test #3:

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

input:

4 2 1
0 0
4 0
4 4
0 4

output:

0.250000000000000
0.500000000000000
0
0.250000000000000

result:

ok correct

Test #4:

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

input:

5 4 3
0 2
0 -1
5 -2
5 4
2 5

output:

0
0.200000000000000
0
0.800000000000000
0

result:

ok correct

Test #5:

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

input:

4 1 1
0 0
2 0
2 2
0 2

output:

0.500000000000000
0
0.500000000000000
0

result:

ok correct

Test #6:

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

input:

10 9999 9999
10000 10000
9999 10000
3232 9480
1381 8103
-1339 138
-1309 -13
0 -1500
2092 -2093
3409 -1844
10000 0

output:

0
0.999899999878296
0
0
0.000000008819131
0
0
0
0
0.000099991302573

result:

ok correct

Test #7:

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

input:

4 3 10
-10000 -10000
10000 -10000
10000 10000
-10000 10000

output:

0.499500000000000
0
0.500150000000000
0.000350000000000

result:

ok correct

Test #8:

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

input:

4 9999 9997
-10000 -10000
10000 -10000
10000 10000
-10000 10000

output:

0.000050000000000
0.000100000000000
0.999850000000000
0

result:

ok correct

Test #9:

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

input:

3 -9999 -9999
-10000 -10000
10000 9999
9999 10000

output:

0.999949998749969
0.000025000625016
0.000025000625016

result:

ok correct

Test #10:

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

input:

3 9999 9999
-10000 -10000
10000 9999
9999 10000

output:

0.000025000625016
0.499987499687492
0.499987499687492

result:

ok correct

Test #11:

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

input:

4 0 0
-1 0
0 -1
1 0
0 1

output:

0.500000000000000
0
0.500000000000000
0

result:

ok correct

Test #12:

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

input:

3 -9999 -9999
-10000 -9999
-9998 -10000
-9999 -9998

output:

0.333333333333333
0.333333333333333
0.333333333333333

result:

ok correct

Test #13:

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

input:

10 501 -4883
-9800 -648
-9220 -7020
-8681 -8394
5123 -9714
9084 -6948
9781 -1791
9068 9943
1486 9788
-567 9580
-5387 9042

output:

0.194550717707994
0
0
0.641917442173680
0
0
0
0
0
0.163531840118326

result:

ok correct

Test #14:

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

input:

10 -2427 6309
-9274 4206
-7424 -9149
8531 -9126
9808 -8029
9830 -2712
8814 5816
6395 9256
3809 9060
-7269 7947
-8325 7570

output:

0.189938638380198
0
0
0
0
0.354644481464660
0
0
0
0.455416880155142

result:

ok correct

Test #15:

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

input:

10 9903 9929
9900 9964
9904 9907
9913 9901
9982 9903
9985 9919
9985 9940
9984 9952
9978 9971
9917 9989
9900 9988

output:

0.344246959775491
0.626753975678204
0
0
0
0
0
0
0.028999064546305
0

result:

ok correct

Test #16:

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

input:

4 -4763 -1481
-9789 3330
-1245 -9824
8612 5658
-6270 9777

output:

0.266668487680643
0.486648041422524
0
0.246683470896833

result:

ok correct

Test #17:

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

input:

4 -5828 -2734
-9581 -7886
6814 -6138
2044 7759
-2078 9814

output:

0.672441810080363
0
0.314248156485436
0.013310033434201

result:

ok correct

Test #18:

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

input:

5 -30 -61
-94 -51
61 -87
94 -43
41 14
-50 64

output:

0.559276624246484
0.401875418620228
0
0
0.038847957133289

result:

ok correct

Test #19:

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

input:

5 9994 9996
9991 9997
9996 9992
9999 9990
9999 9999
9993 9999

output:

0.300000000000000
0
0.266666666666667
0
0.433333333333333

result:

ok correct

Test #20:

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

input:

6 -2222 4045
-7346 -9353
4845 -9940
6164 3951
5835 7542
4373 9868
-5991 8668

output:

0.283215620407687
0
0
0
0.400690579472445
0.316093800119868

result:

ok correct

Test #21:

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

input:

6 8521 1820
-9823 -9510
6717 -8681
9568 -4633
8747 9429
3592 9545
-5415 7112

output:

0.034064595118078
0
0.495224764120233
0.470710640761689
0
0

result:

ok correct

Test #22:

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

input:

7 -5410 5191
-9950 739
-6207 -9764
6979 -9287
9232 -4700
8031 4301
5709 7849
-8440 8438

output:

0.402077138244325
0
0
0
0
0.257059614018583
0.340863247737093

result:

ok correct

Test #23:

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

input:

7 5724 -4583
-9946 -7548
-7002 -9087
-4368 -9593
6664 -9627
9213 -5140
8776 6804
-9841 9513

output:

0.124032149043788
0
0
0
0.817572340487541
0
0.058395510468671

result:

ok correct

Test #24:

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

input:

8 -7052 -7123
-9576 -143
-6958 -9612
-5370 -9798
5969 -7902
9491 -7205
9451 -982
6556 9714
-7662 8751

output:

0.198549969334037
0.769941682307482
0
0
0
0
0.031508348358481
0

result:

ok correct

Test #25:

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

input:

8 4874 -8587
-9479 255
-9246 -5912
-8999 -9756
7705 -9572
9650 -7812
9687 6292
9180 9406
-8195 9864

output:

0.101453198258316
0
0.065111843937327
0.833434957804358
0
0
0
0

result:

ok correct

Test #26:

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

input:

9 -7531 9127
-9994 2777
-8860 -5799
-5350 -7348
-2613 -8020
7132 -9208
8756 -8852
9665 -402
9521 9190
-9028 9952

output:

0.105826215781969
0
0
0
0
0
0
0.086216406514927
0.807957377703104

result:

ok correct

Test #27:

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

input:

9 -9994 -9998
-10000 -9996
-9996 -10000
-9992 -10000
-9991 -9998
-9991 -9994
-9993 -9992
-9995 -9991
-9997 -9991
-9999 -9992

output:

0.055555555555556
0
0.722222222222222
0
0
0
0
0
0.222222222222222

result:

ok correct

Test #28:

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

input:

9 7575 3946
-9632 8949
-8177 1024
-6420 -4609
-5610 -6935
-2573 -9154
3538 -9808
8894 -3544
7802 8804
-4290 9596

output:

0.037690854784993
0
0
0
0
0
0.393866632162603
0.568442513052404
0

result:

ok correct

Test #29:

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

input:

8 1 3
1000 2000
-1000 2000
-2000 1000
-2000 -1000
-1000 -2000
1000 -2000
2000 -1000
2000 1000

output:

0
0
0.001250000000000
0.498500000000000
0
0
0
0.500250000000000

result:

ok correct

Test #30:

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

input:

8 1000 1000
1100 1200
900 1200
800 1100
800 900
900 800
1100 800
1200 900
1200 1100

output:

0
0
0
0.500000000000000
0
0
0
0.500000000000000

result:

ok correct

Test #31:

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

input:

9 2 8
0 0
9 0
9 1
8 4
7 6
6 7
4 8
1 9
0 9

output:

0
0
0.125000000000000
0
0
0
0
0.875000000000000
0

result:

ok correct

Test #32:

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

input:

5 2 6
0 0
1 2
2 5
3 9
4 14

output:

0.333333333333333
0
0
0.666666666666667
0

result:

ok correct

Test #33:

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

input:

3 9999 9999
9999 10000
0 -1500
10000 0

output:

0.999900001499978
0.000000009999850
0.000099988500172

result:

ok correct

Test #34:

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

input:

3 9999 9999
10000 0
9999 10000
0 -1500

output:

0.000099988500172
0.999900001499978
0.000000009999850

result:

ok correct

Test #35:

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

input:

3 9999 9999
0 -1500
10000 0
9999 10000

output:

0.000000009999850
0.000099988500172
0.999900001499978

result:

ok correct

Test #36:

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

input:

3 0 0
1 0
-1 10000
-1 -10000

output:

0.500000000000000
0.250000000000000
0.250000000000000

result:

ok correct

Test #37:

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

input:

3 9999 -1
0 1
-10000 -2
10000 -1

output:

0.000020000000000
0.000040000000000
0.999940000000000

result:

ok correct

Test #38:

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

input:

3 9999 0
-10000 1
-10000 -1
10000 0

output:

0.000025000000000
0.000025000000000
0.999950000000000

result:

ok correct

Test #39:

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

input:

3 -9999 0
-10000 1
-10000 -1
10000 0

output:

0.499975000000000
0.499975000000000
0.000050000000000

result:

ok correct