QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133872 | #6260. Historic Exhibition | KhNURE_KIVI# | WA | 1ms | 3464kb | C++23 | 7.5kb | 2023-08-02 16:10:29 | 2023-08-02 16:10:32 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#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;
vector <point> a(n);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a[i].x = x;
}
for (int i = 0; i < n; i++) {
int y;
cin >> y;
a[i].y = y;
a[i].id = i;
}
convex_hull(a);
int x, y;
cin >> x >> y;
if (len(a) == 1) {
if (a[0].x == x && a[0].y == y) {
cout << "Yes\n";
for (int i = 0; i < n; i++) {
if (i == a[0].id) {
cout << "1 ";
}
else {
cout << "0 ";
}
}
cout << '\n';
}
else {
cout << "No\n";
}
return 0;
}
int m = len(a);
for (int i = 0; i < m; i++) {
if (a[i].x == x && a[i].y == y) {
cout << "Yes\n";
for (int j = 0; j < n; j++) {
if (j == a[i].id) {
cout << "1 ";
}
else {
cout << "0 ";
}
}
cout << '\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;
}
cout << "Yes\n";
for (int k = 0; k < n; k++) {
if (k == a[i].id) {
cout << p << ' ';
}
else if (k == a[j].id) {
cout << 1 - p << ' ';
}
else {
cout << "0 ";
}
}
cout << '\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])) {
cout << "Yes\n";
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) << ' ';
}
else if (i1 == a[j].id) {
cout << (1 - p1) * (1 - p2) << ' ';
}
else if (i1 == a[k].id) {
cout << p2 << ' ';
}
else {
cout << "0 ";
}
}
cout << '\n';
return 0;
}
}
}
}
cout << "No\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3464kb
input:
4 3 1 2 4 5 2 3 2 2 1 2 3
output:
No
result:
wrong output format Expected integer, but "No" found