QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#583404#9172. Alternating Cycleucup-team4435#WA 1ms5956kbC++205.5kb2024-09-22 19:50:222024-09-22 19:50:22

Judging History

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

  • [2024-09-22 19:50:22]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5956kb
  • [2024-09-22 19:50:22]
  • 提交

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) {
        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;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

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

output:

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

result:

ok Everything ok

Test #2:

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

input:

4
0 0
0 1
1 0
1 1

output:

-1

result:

ok Everything ok

Test #3:

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

input:

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

output:

6
767007508 725151476
697948407 601311897
593914132 156628727
110658137 698550461
294286621 249587903
361249906 42266067

result:

ok Everything ok

Test #4:

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

input:

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

output:

6
870407732 947373192
362190573 311657719
474856219 425123887
908809410 529664178
290489622 819212758
792350850 916217578

result:

ok Everything ok

Test #5:

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

input:

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

output:

6
588325559 932595937
608245683 644278574
995422410 349401528
456106901 458016459
47664912 379660370
186290410 443720168

result:

ok Everything ok

Test #6:

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

input:

9
224922093 516980257
696767119 51724974
580229972 266190050
593338977 91401448
843660194 888238866
108985009 509903616
591194203 709542627
225635675 932844521
618628214 461769776

output:

6
618628214 461769776
843660194 888238866
591194203 709542627
224922093 516980257
580229972 266190050
593338977 91401448

result:

ok Everything ok

Test #7:

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

input:

9
107211982 359332853
695837148 142871176
605573313 162288860
509232688 314721021
396930687 132108911
205496625 287885162
183997430 822925807
474429448 221410467
801183393 664390830

output:

6
695837148 142871176
509232688 314721021
183997430 822925807
605573313 162288860
474429448 221410467
107211982 359332853

result:

ok Everything ok

Test #8:

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

input:

9
284469163 791620032
31343664 160388450
294480166 689791450
351497471 948106011
245168471 81011666
7040948 65866709
481833366 304905205
91819440 215009122
983738573 203448372

output:

6
294480166 689791450
351497471 948106011
91819440 215009122
7040948 65866709
481833366 304905205
983738573 203448372

result:

ok Everything ok

Test #9:

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

input:

9
461726344 560343699
661817474 882938432
319823507 217294040
562358475 876458292
93406256 619849004
513617981 138815548
484702011 418288384
340613213 503575069
534889971 406069427

output:

6
562358475 876458292
461726344 560343699
319823507 217294040
661817474 882938432
534889971 406069427
513617981 138815548

result:

ok Everything ok

Test #10:

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

input:

9
638983525 992630879
660887503 900455706
713763069 113392850
404623258 99777864
646676749 863719050
315162304 548200875
782537947 195235074
958003206 160737235
422477859 945126970

output:

6
958003206 160737235
782537947 195235074
404623258 99777864
660887503 900455706
646676749 863719050
315162304 548200875

result:

ok Everything ok

Test #11:

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

input:

9
521273414 129950765
291361311 623005687
107702630 935862733
320516969 733162854
494914533 812621805
453143117 621149714
711777663 308618254
206796978 449303183
678661966 147748023

output:

6
494914533 812621805
453143117 621149714
521273414 129950765
291361311 623005687
107702630 935862733
320516969 733162854

result:

ok Everything ok

Test #12:

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

input:

8
563402439 725563321
430451262 152240853
780848346 860389268
888894820 499849356
415818421 408692535
840472921 429397462
326582722 561795426
53848834 517062841

output:

6
780848346 860389268
563402439 725563321
53848834 517062841
326582722 561795426
430451262 152240853
415818421 408692535

result:

ok Everything ok

Test #13:

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

input:

8
740659620 157850500
839586707 169758127
469755198 387891858
436192311 428201637
264056205 652562581
936984536 838782790
624418658 970145897
966206119 805628788

output:

-1

result:

ok Everything ok

Test #14:

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

input:

8
917916801 295170387
470060516 892308109
495098540 283990668
647053314 356553918
817326699 191399918
443561568 911731629
922254594 157158003
920032600 94194734

output:

-1

result:

ok Everything ok

Test #15:

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

input:

8
800206690 432490275
469130545 909825383
889038101 106460550
489318097 284906199
665564483 140302673
245105891 689713175
925123238 565508474
832389884 456389610

output:

-1

result:

ok Everything ok

Test #16:

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

input:

8
272431162 201213942
99604353 632375365
914381443 338995849
700179101 213258480
218834975 384172719
751682924 762662014
222959174 47487873
786216365 744955557

output:

-1

result:

ok Everything ok

Test #17:

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

input:

8
154721052 338533829
803707091 18488857
308321004 530061950
542443884 141610761
772105469 628042765
553227248 540643561
447166182 455838344
698573649 33521503

output:

6
698573649 33521503
542443884 141610761
154721052 338533829
772105469 628042765
553227248 540643561
308321004 530061950

result:

ok Everything ok

Test #18:

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

input:

8
331978233 475853717
434180900 741038840
997227857 57564540
384708667 774995751
620343253 871912811
354771571 950028888
450034826 937817743
947367422 322087450

output:

-1

result:

ok Everything ok

Test #19:

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

input:

8
214268122 908140896
64654708 758556113
727603907 585067131
595569671 998315324
468581038 115782857
861348604 728010435
747870762 346168213
196161194 610653397

output:

-1

result:

ok Everything ok

Test #20:

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

input:

8
686492595 45460782
63724737 776073387
121543467 776133233
142867162 926667605
21851530 359652903
589263999 800959274
45706698 828147612
108518478 267815563

output:

6
45706698 828147612
686492595 45460782
121543467 776133233
142867162 926667605
21851530 359652903
63724737 776073387

result:

ok Everything ok

Test #21:

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

input:

7
728621620 936040631
202814687 10341261
89656474 700659768
79841231 324757887
942755419 324319853
681626511 240610802
660511757 417761272

output:

-1

result:

ok Everything ok

Test #22:

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

input:

7
610911509 704764298
243353913 27858534
778563328 228162358
627138724 958142877
790993203 273222607
483170835 313559641
589751473 194707963

output:

6
483170835 313559641
243353913 27858534
589751473 194707963
778563328 228162358
610911509 704764298
627138724 958142877

result:

ok Everything ok

Test #23:

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

input:

7
493201398 842084186
242423942 750408517
172502889 755664949
132967018 550058669
639230987 812059946
284715158 91541188
887587409 308091142

output:

-1

result:

ok Everything ok

Test #24:

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

input:

7
965425871 274371364
872897751 767925791
197846230 651763759
680264510 183443658
192501480 55929991
791292191 164490026
890456054 85037832

output:

-1

result:

ok Everything ok

Test #25:

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

input:

7
847715760 116723959
871967780 490475772
591785792 179266348
522529294 111795939
40739264 4832745
592836514 647504282
188291989 198421011

output:

-1

result:

ok Everything ok

Test #26:

score: -100
Wrong Answer
time: 0ms
memory: 5744kb

input:

7
24972940 254043847
207474297 171556557
617129133 1736230
733390297 40148220
888977050 543670083
689348130 351856901
486127925 975367703

output:

6
207474297 171556557
0 0
888977050 543670083
689348130 351856901
733390297 40148220
24972940 254043847

result:

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