QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133872#6260. Historic ExhibitionKhNURE_KIVI#WA 1ms3464kbC++237.5kb2023-08-02 16:10:292023-08-02 16:10:32

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:10:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3464kb
  • [2023-08-02 16:10:29]
  • 提交

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