QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#583399#9172. Alternating Cycleucup-team4435#WA 1ms5764kbC++205.6kb2024-09-22 19:49:162024-09-22 19:49:17

Judging History

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

  • [2024-09-22 19:49:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5764kb
  • [2024-09-22 19:49:16]
  • 提交

answer

#pragma GCC optimize("Ofast")

#include "bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

int Bit(int mask, int b) { return (mask >> b) & 1; }

template<class T>
bool ckmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool ckmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
    --l;
    while (r - l > 1) {
        T mid = l + (r - l) / 2;
        if (predicat(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}


template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
    return FindFirstTrue(l, r, predicat) - 1;
}


const ll INF = 2e18;
const int INFi = 1e9;
const int N = 3e5 + 5;
const int LG = 20;

struct Point {
    int x, y;

    Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}

    Point operator-(const Point &oth) const {
        return {x - oth.x, y - oth.y};
    }


    ll operator*(const Point &oth) const {
        return 1ll * x * oth.y - 1ll * y * oth.x;
    }

    ll length() const {
        return 1ll * x * x + 1ll * y * y;
    }
};

using pt = Point;

vector<pt> A;

int ang_type(int a, int b, int c) {
    ll v = (A[b] - A[a]) * (A[c] - A[b]);
    if (v > 0) return 1;
    if (v < 0) return 2;
    return 0;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int SZ = 500;
char tp[SZ][SZ][SZ];

pair<vector<Point>, vector<Point>> convex_hull(vector<Point> a) {
    int n = a.size();
    for (int i = 1; i < n; i++) {
        if (make_pair(a[i].x, a[i].y) < make_pair(a[0].x, a[0].y)) {
            swap(a[i], a[0]);
        }
    }

    sort(1 + all(a), [&](Point p, Point q) {
        p = p - a[0];
        q = q - a[0];
        ll prod = p * q;
        if (prod != 0) {
            return prod > 0;
        }
        return p.length() < q.length();
    });

    vector<Point> hull = {a[0], a[1]}, rem;
    for (int i = 2; i < n; i++) {
        while ((hull.back() - hull[int(hull.size()) - 2]) * (a[i] - hull.back()) < 0) {
            rem.push_back(hull.back());
            hull.pop_back();
        }
        hull.push_back(a[i]);
    }
    return {hull, rem};
}

void solve() {
    int n;
    cin >> n;
    A.resize(n);
    rep(i, n) cin >> A[i].x >> A[i].y;

    vector<vector<pt>> keks;
    while (keks.size() < 5 && !A.empty()) {
        auto [lol, kek] = convex_hull(A);
        keks.push_back(lol);
        A = kek;
    }
    if (!A.empty()) {
        keks.push_back(A);
    }
    A.clear();
    rep(j, keks.size()) {
        shuffle(all(keks[j]), rng);
    }
    rep(i, n) {
        rep(j, keks.size()) {
            if (keks[j].empty()) continue;
            A.push_back(keks[j].back());
            keks[j].pop_back();
        }
    }

    for (int s0 = 0; s0 < n; ++s0) {
        if (clock() / (1.0 * CLOCKS_PER_SEC) >= 1.8) {
            break;
        }
        for(int i = 0; i < s0; ++i) {
            for(int j = 0; j < s0; ++j) {
                if (i == j) continue;
                tp[i][j][s0] = ang_type(i, j, s0);
                tp[i][s0][j] = ang_type(i, s0, j);
                tp[s0][i][j] = ang_type(s0, i, j);
            }
        }
        rep(s1, s0) {
            rep(s2, s0) {
                if (s2 == s1) continue;
                rep(s3, s0) {
                    if (s3 == s1 || s3 == s2 || tp[s0][s1][s2] == tp[s1][s2][s3]) continue;
                    rep(s4, s0) {
                        if (s4 == s3 || s4 == s2 || s4 == s1 || tp[s1][s2][s3] == tp[s2][s3][s4]) continue;
                        rep(s5, s1) {
                            if (s1 == s5 || s2 == s5 || s5 == s3 || s5 == s4 || tp[s2][s3][s4] == tp[s3][s4][s5] || tp[s3][s4][s5] == tp[s4][s5][s0] || tp[s4][s5][s0] == tp[s5][s0][s1] || tp[s5][s0][s1] == tp[s0][s1][s2]) continue;
                            cout << "6\n";
                            cout << A[s0].x << ' ' << A[s0].y << '\n';
                            cout << A[s1].x << ' ' << A[s1].y << '\n';
                            cout << A[s2].x << ' ' << A[s2].y << '\n';
                            cout << A[s3].x << ' ' << A[s3].y << '\n';
                            cout << A[s4].x << ' ' << A[s4].y << '\n';
                            cout << A[s5].x << ' ' << A[s5].y << '\n';
                            return;
                        }
                    }
                }
            }
        }
    }

    cout << "-1\n";
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(12) << fixed;
    int t = 1;
//    cin >> t;
    rep(i, t) {
        solve();
    }
//    cout << sizeof(a) / 1'000'000 << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5752kb

input:

6
10 15
20 15
15 23
0 31
15 0
30 30

output:

6
20 15
15 0
10 15
0 31
15 23
30 30

result:

ok Everything ok

Test #2:

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

input:

4
0 0
0 1
1 0
1 1

output:

-1

result:

ok Everything ok

Test #3:

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

input:

9
693150551 810053304
26684055 999173154
767007508 725151476
697948407 601311897
593914132 156628727
294286621 249587903
361249906 42266067
110658137 698550461
923704821 886066345

output:

6
361249906 42266067
697948407 601311897
923704821 886066345
693150551 810053304
26684055 999173154
294286621 249587903

result:

ok Everything ok

Test #4:

score: 0
Accepted
time: 1ms
memory: 5692kb

input:

9
870407732 947373192
362190573 311657719
792350850 916217578
908809410 529664178
147184624 105531482
800863654 27569449
290489622 819212758
64484618 355712627
474856219 425123887

output:

6
792350850 916217578
870407732 947373192
362190573 311657719
474856219 425123887
800863654 27569449
290489622 819212758

result:

ok Everything ok

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 5764kb

input:

9
47664912 379660370
66293309 34207701
186290410 443720168
456106901 458016459
995422410 349401528
602407977 731922069
588325559 932595937
608245683 644278574
657411398 627744942

output:

6
47664912 379660370
186290410 443720168
602407977 731922069
0 0
66293309 34207701
995422410 349401528

result:

wrong answer Points do not come from the original point set, or are not unique