QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133875 | #6263. Keep Him Inside | KhNURE_KIVI# | AC ✓ | 1ms | 3852kb | C++14 | 7.8kb | 2023-08-02 16:17:04 | 2023-08-02 16:17:06 |
Judging History
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