QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783234#6263. Keep Him Inside353cerega#AC ✓0ms4080kbC++142.1kb2024-11-26 02:29:452024-11-26 02:29:46

Judging History

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

  • [2024-11-26 02:29:46]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:4080kb
  • [2024-11-26 02:29:45]
  • 提交

answer

#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

#define X first
#define Y second


const ll mod = 1000000007;
//const ll mod = 998244353;



ll pew(ll a, ll b) {
    ll res = 1;
    while (b>0) {
        if (b&1) res = res*a%mod;
        b >>= 1;
        a = a*a%mod;
    }
    return res;
}



ll area(pair<ll,ll> a, pair<ll,ll> b, pair<ll,ll> c) {
    return (b.X-a.X)*(c.Y-a.Y)-(b.Y-a.Y)*(c.X-a.X);
}

void solve() {
    ll n;
    pair<ll,ll> st;
    cin >> n >> st.X >> st.Y;
    vector<pair<ld,ld>> a(n);
    for (ll i=0;i<n;i++) {
        cin >> a[i].X >> a[i].Y;
    }
    cout.precision(20);
    for (ll t=1;t+1<n;t++) {
        vector<ll> cur = {0,t,t+1};
        ll F = 0;
        for (ll w=0;w<3;w++) {
            if (area(a[cur[w]],a[cur[(w+1)%3]],st)<0) F = 1;
        }
        if (F==1) continue;
        ll k = 3;
        vector<vector<ld>> A(k,vector<ld>(k+1));
        for (ll i=0;i<k;i++) {
            A[0][i] = a[cur[i]].X;
            A[1][i] = a[cur[i]].Y;
            A[2][i] = 1;
        }
        A[0][3] = st.X, A[1][3] = st.Y, A[2][3] = 1;
        for (ll i=0;i<k;i++) {
            for (ll j=i+1;j<k;j++) {
                if (abs(A[j][i])>abs(A[i][i])) swap(A[i],A[j]);
            }
            for (ll j=i+1;j<k;j++) {
                ld r = A[j][i]/A[i][i];
                for (ll w=i;w<=k;w++) A[j][w] -= r*A[i][w];
            }
        }
        vector<ld> A0(3);
        for (ll i=k-1;i>=0;i--) {
            A0[i] = A[i][k];
            for (ll j=i+1;j<k;j++) A0[i] -= A0[j]*A[i][j];
            A0[i] /= A[i][i];
        }
        vector<ld> ans(n);
        for (ll w=0;w<3;w++) ans[cur[w]] = A0[w];
        for (ll i=0;i<n;i++) cout << ans[i] << "\n";
        return;
    }
    assert(false);
}

int main() {
    ios_base::sync_with_stdio(false);
    int T = 1;
    //cin >> T;
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

0.5
0.25
0.25

result:

ok correct

Test #2:

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

input:

3 1 1
0 0
3 0
0 3

output:

0.33333333333333333329
0.33333333333333333334
0.33333333333333333334

result:

ok correct

Test #3:

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

input:

4 2 1
0 0
4 0
4 4
0 4

output:

0.5
0.25
0.25
0

result:

ok correct

Test #4:

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

input:

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

output:

0.20000000000000000004
0
0.1
0.69999999999999999999
0

result:

ok correct

Test #5:

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

input:

4 1 1
0 0
2 0
2 2
0 2

output:

0.5
0
0.5
0

result:

ok correct

Test #6:

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

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.99990656173241766503
0
0
0
0
5.0127825956188275723e-05
4.3310441626146670224e-05
0
0
0

result:

ok correct

Test #7:

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

input:

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

output:

0.49949999999999999999
0
0.50015000000000000001
0.00034999999999999999999

result:

ok correct

Test #8:

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

input:

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

output:

5.0000000000000000001e-05
0.0001
0.99984999999999999999
0

result:

ok correct

Test #9:

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

input:

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

output:

0.99994999874996874921
2.5000625015625388444e-05
2.5000625015625388445e-05

result:

ok correct

Test #10:

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

input:

3 9999 9999
-10000 -10000
10000 9999
9999 10000

output:

2.5000625015625388414e-05
0.49998749968749218732
0.49998749968749218729

result:

ok correct

Test #11:

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

input:

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

output:

0.5
-0
0.5
0

result:

ok correct

Test #12:

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

input:

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

output:

0.33333333333333343203
0.333333333333333432
0.33333333333333313596

result:

ok correct

Test #13:

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

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.41353931864876883339
0
0
0.19533539677774535468
0.39112528457348581188
0
0
0
0
0

result:

ok correct

Test #14:

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

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.56681787265694868712
0
0
0
0
0.024584227640235212194
0.4085978997028161007
0
0
0

result:

ok correct

Test #15:

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

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.39263803680981593076
0.54396728016359932226
0.063394683026584747003
0
0
0
0
0
0
0

result:

ok correct

Test #16:

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

input:

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

output:

0.52189087424952331894
0.382640359433349032
0.095468766317127649075
0

result:

ok correct

Test #17:

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

input:

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

output:

0.67244181008036326661
0
0.3142481564854356112
0.013310033434201122174

result:

ok correct

Test #18:

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

input:

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

output:

0.60714285714285714287
0.29870129870129870128
0.094155844155844155864
0
0

result:

ok correct

Test #19:

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

input:

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

output:

0.62499999999999999518
0
0.19444444444444448232
0.18055555555555552256
0

result:

ok correct

Test #20:

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

input:

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

output:

0.28321562040768734141
0
0
0
0.40069057947244464949
0.31609380011986800912

result:

ok correct

Test #21:

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

input:

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

output:

0.034064595118078156763
0
0.49522476412023309545
0.47071064076168874776
0
0

result:

ok correct

Test #22:

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

input:

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

output:

0.40207713824432454174
0
0
0
0
0.25705961401858294283
0.34086324773709251543

result:

ok correct

Test #23:

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

input:

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

output:

0.18021522032839452114
0
0
0
0.73681774596842614143
0.082967033703179337534
0

result:

ok correct

Test #24:

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

input:

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

output:

0.27045330582692959033
0.34286737763975701698
0.38667931653331339266
0
0
0
0
0

result:

ok correct

Test #25:

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

input:

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

output:

0.10145319825831567034
0
0.065111843937326599622
0.83343495780435772991
0
0
0
0

result:

ok correct

Test #26:

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

input:

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

output:

0.10582621578196872348
0
0
0
0
0
0
0.086216406514927046609
0.80795737770310422997

result:

ok correct

Test #27:

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

input:

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

output:

0.29999999999999999191
0
0.29999999999999991056
0.40000000000000009756
0
0
0
0
0

result:

ok correct

Test #28:

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

input:

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

output:

0.037690854784992695924
0
0
0
0
0
0.39386663216260316979
0.56844251305240413422
0

result:

ok correct

Test #29:

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

input:

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

output:

0.50066666666666666664
0
0
0.00033333333333333333335
0.49900000000000000001
0
0
0

result:

ok correct

Test #30:

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

input:

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

output:

0.5
0
0
-0
0.5
0
0
0

result:

ok correct

Test #31:

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

input:

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

output:

0.071428571428571428564
0
0
0
0
0
0.35714285714285714287
0.57142857142857142856
0

result:

ok correct

Test #32:

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

input:

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

output:

0.33333333333333333332
0
0
0.66666666666666666668
0

result:

ok correct

Test #33:

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

input:

3 9999 9999
9999 10000
0 -1500
10000 0

output:

0.99990000149997750034
9.9998500022178898621e-09
9.9988500172497440658e-05

result:

ok correct

Test #34:

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

input:

3 9999 9999
10000 0
9999 10000
0 -1500

output:

9.9988500172497385422e-05
0.99990000149997750034
9.9998500022499631506e-09

result:

ok correct

Test #35:

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

input:

3 9999 9999
0 -1500
10000 0
9999 10000

output:

9.9998500022735470336e-09
9.9988500172497385422e-05
0.99990000149997750034

result:

ok correct

Test #36:

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

input:

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

output:

0.5
0.25
0.25

result:

ok correct

Test #37:

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

input:

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

output:

2.0000000000000052458e-05
4.0000000000000035526e-05
0.99994000000000000001

result:

ok correct

Test #38:

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

input:

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

output:

2.5e-05
2.4999999999999984257e-05
0.99994999999999999998

result:

ok correct

Test #39:

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

input:

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

output:

0.49997499999999999999
0.49997499999999999999
4.999999999999999562e-05

result:

ok correct