QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#320162#8209. Curly Palindromesucup-team133#AC ✓1ms3888kbC++234.4kb2024-02-03 14:15:402024-02-03 14:15:40

Judging History

This is the latest submission verdict.

  • [2024-02-03 14:15:40]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3888kb
  • [2024-02-03 14:15:40]
  • Submitted

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

#include <type_traits>

namespace geometry {

template <typename T> struct Point {
    static T EPS;

    static void set_eps(T eps) { EPS = eps; }

    T x, y;

    Point() {}

    Point(T x, T y) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }

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

    Point operator*(T t) const { return Point(x * t, y * t); }

    Point operator/(T t) const { return Point(x / t, y / t); }

    bool operator==(const Point& p) const { return x == p.x and y == p.y; }

    bool operator!=(const Point& p) const { return not((*this) == p); }

    bool operator<(const Point& p) const { return x != p.x ? x < p.x : y < p.y; }

    friend std::istream& operator>>(std::istream& is, Point& p) { return is >> p.x >> p.y; }

    friend std::ostream& operator<<(std::ostream& os, const Point& p) { return os << p.x << ' ' << p.y; }

    T norm() { return std::sqrt(x * x + y * y); }

    T norm2() { return x * x + y * y; }

    T arg() { return std::atan2(y, x); }

    T dot(const Point& p) { return x * p.x + y * p.y; }

    T det(const Point& p) { return x * p.y - y * p.x; }

    Point perp() { return Point(-y, x); }

    Point unit() { return *this / norm(); }

    Point normal() { return perp().unit(); }

    Point rotate(T rad) { return Point(std::cos(rad) * x - std::sin(rad) * y, std::sin(rad) * x + std::cos(rad) * y); }
};

template <> double Point<double>::EPS = 1e-9;
template <> long double Point<long double>::EPS = 1e-12;
template <> int Point<int>::EPS = 0;
template <> long long Point<long long>::EPS = 0;

template <typename T> int sgn(T x) { return x < -Point<T>::EPS ? -1 : x > Point<T>::EPS ? 1 : 0; }

}  // namespace geometry

namespace geometry {

enum Position { COUNTER_CLOCKWISE = +1, CLOCKWISE = -1, ONLINE_BACK = +2, ONLINE_FRONT = -2, ON_SEGMENT = 0 };

template <typename T> Position ccw(const Point<T>& a, Point<T> b, Point<T> c) {
    b = b - a;
    c = c - a;
    if (sgn(b.det(c)) == 1) return COUNTER_CLOCKWISE;
    if (sgn(b.det(c)) == -1) return CLOCKWISE;
    if (sgn(b.dot(c)) == -1) return ONLINE_BACK;
    if (b.norm2() < c.norm2()) return ONLINE_FRONT;
    return ON_SEGMENT;
}

}  // namespace geometry

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

using namespace geometry;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Point<ll>> ps;
    vector<char> labels(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y >> labels[i];
        ps.emplace_back(x, y);
    }

    auto f = [&](int i, int j, int k) {
        int res = ccw(ps[i], ps[j], ps[k]);
        if (res == Position::COUNTER_CLOCKWISE) return 1;
        if (res == Position::CLOCKWISE) return -1;
        return 0;
    };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (labels[i] != labels[j]) continue;
            for (int k = 0; k < n; k++) {
                if (i == k or j == k) continue;
                if (f(i, j, k) and f(j, k, i) and f(k, i, j)) {
                    cout << "Infinity\n";
                    return 0;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (labels[i] == labels[j]) {
                cout << 2 << '\n';
                return 0;
            }
        }
    }

    cout << 1 << '\n';
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

4
0 0 o
1 1 c
2 2 p
3 3 c

output:

2

result:

ok single line: '2'

Test #2:

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

input:

3
2 3 e
3 2 e
8 9 e

output:

Infinity

result:

ok single line: 'Infinity'

Test #3:

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

input:

3
0 0 p
1 1 c
2 2 o

output:

1

result:

ok single line: '1'

Test #4:

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

input:

3
1000000000 1000000000 a
0 1000000000 b
1000000000 0 a

output:

Infinity

result:

ok single line: 'Infinity'

Test #5:

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

input:

5
10 0 a
20 0 b
30 0 c
41 0 d
42 0 e

output:

1

result:

ok single line: '1'

Test #6:

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

input:

6
999999999 1000000000 b
0 0 a
1 1 a
2 2 c
3 3 d
4 4 e

output:

Infinity

result:

ok single line: 'Infinity'

Test #7:

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

input:

1
52524 6287 o

output:

1

result:

ok single line: '1'

Test #8:

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

input:

100
620277501 352211578 a
588745387 204868067 a
279087773 862840409 a
368942847 32429835 a
986161321 811576403 a
108066135 22119129 a
854047430 512772131 a
196877261 824967276 a
467809712 903492464 a
549499819 662329823 a
358024530 364859507 a
323528347 87306983 a
346602511 829302399 a
216164493 243...

output:

Infinity

result:

ok single line: 'Infinity'

Test #9:

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

input:

100
964906060 545884156 b
525844995 678718384 a
767874103 529057847 b
335899480 961060244 b
458611128 578152716 b
449062933 779433747 a
672526007 895103745 b
111902255 436806217 a
873636242 773662394 a
250185459 522336127 a
975489206 77297854 b
54583166 952092302 a
863604349 909716224 a
70170689 533...

output:

Infinity

result:

ok single line: 'Infinity'

Test #10:

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

input:

100
197441358 388148939 b
374082779 922588431 b
545855650 531926491 b
953289473 249626190 a
997668672 445922624 b
941714598 963970889 a
252303702 946260915 c
705178416 744961339 a
889814639 633539049 b
526449032 53699804 b
937365752 742338401 b
294384909 349114633 b
245948038 979810742 c
46734037 30...

output:

Infinity

result:

ok single line: 'Infinity'

Test #11:

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

input:

100
388507460 599009943 b
222320564 871491185 b
323837196 829762427 d
202083245 906788357 c
200289725 313692532 c
65770043 517104251 d
905710326 292385376 b
3487284 126745388 b
495927620 829852193 b
97679895 880030775 b
677903935 407378948 d
534186652 672508037 b
964728216 976276332 b
391893605 5597...

output:

Infinity

result:

ok single line: 'Infinity'

Test #12:

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

input:

100
916010051 146307434 c
480623765 410328522 d
28189815 127598363 c
745844310 195354303 c
739347268 591527857 d
484792781 775270322 b
190520730 638509838 d
6828862 434900510 b
512106017 321132628 e
668910759 411394452 b
639780481 72419495 a
773988394 364497659 c
347071905 341338141 d
368456952 5180...

output:

Infinity

result:

ok single line: 'Infinity'

Test #13:

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

input:

100
86229674 966475154 g
188905509 869037044 j
206431319 885238671 g
384203494 608011484 b
94907195 845681979 j
93491181 751753218 f
658592436 874867662 j
390873056 182636414 b
313350178 5306341 j
964520327 884419573 c
616180319 281427186 e
506244230 796896398 b
427455351 844237339 f
78090262 517379...

output:

Infinity

result:

ok single line: 'Infinity'

Test #14:

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

input:

100
215977786 124594064 t
330805101 191632694 a
89113834 355297431 h
763543468 766857893 i
129574380 326152621 t
980011509 580824171 l
593104211 610936942 p
433305160 169599834 n
169733556 636573400 d
529043807 454466372 h
898931244 35490902 l
277816100 810116698 c
35985918 405195648 i
188992394 893...

output:

Infinity

result:

ok single line: 'Infinity'

Test #15:

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

input:

100
708120351 620407913 n
535329934 654852971 t
609745260 478749536 q
362094763 276915210 s
280981242 647870195 n
936373080 162431905 h
260497437 466345348 o
181689176 124319222 n
488142303 321448453 b
39367382 527550314 k
301142721 730766894 n
126691970 634927413 k
412986447 268439483 x
227790067 4...

output:

Infinity

result:

ok single line: 'Infinity'

Test #16:

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

input:

26
526735598 478961006 a
531191531 475454507 b
378204498 595844306 c
442072871 545584487 d
525250287 480129839 e
498514689 501168833 f
568324306 446233682 g
470293780 523376660 h
554956507 456753179 i
455440670 535064990 j
397513541 580649477 k
612883636 411168692 l
513367799 489480503 m
465837847 5...

output:

1

result:

ok single line: '1'

Test #17:

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

input:

100
548848602 549471818 a
320148329 317853761 b
508881564 508994876 c
704275972 706882148 d
371217322 369574298 e
597697204 598943636 f
624341896 625928264 g
380098886 378569174 h
313487156 311107604 i
553289384 553969256 j
466694135 466269215 k
406743578 405553802 l
488898045 488756405 m
653206979 ...

output:

2

result:

ok single line: '2'

Test #18:

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

input:

100
509098504 507901696 w
513647756 511852544 t
638752186 620500864 f
565964154 557287296 e
438585098 446663552 s
283910530 312334720 l
702441714 675812736 g
295283660 322211840 h
561414902 553336448 b
434035846 442712704 g
688793958 663960192 n
447683602 454565248 o
320304546 343941504 c
540943268 ...

output:

2

result:

ok single line: '2'

Extra Test:

score: 0
Extra Test Passed