QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783234 | #6263. Keep Him Inside | 353cerega# | AC ✓ | 0ms | 4080kb | C++14 | 2.1kb | 2024-11-26 02:29:45 | 2024-11-26 02:29:46 |
Judging History
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