QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#59704#2838. 2D GeometryXrkArul#WA 141ms3672kbC++171.8kb2022-10-31 20:59:482022-10-31 20:59:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-31 20:59:51]
  • 评测
  • 测评结果:WA
  • 用时:141ms
  • 内存:3672kb
  • [2022-10-31 20:59:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using point_t = long long;
constexpr point_t eps = 1e-8;

template<typename T> struct point {
    T x, y;

    point<T> operator-(point a) { return {x - a.x, y - a.y}; }
    T operator^(point a) { return x * a.y - y * a.x; }
    int toleft(point a) { auto t = (*this) ^ a; return (t > eps) - (t < -eps); }
};
using Point = point<point_t>;

#define int long long
signed main() {
    int n; while (cin >> n) {
        vector<Point> p(n);
        for (auto &[x, y] : p) scanf("%lld %lld", &x, &y);

        auto cnt_in_line = [&](int i, int j) {
            Point i_j = p[i] - p[j];
            int res = 0;
            for (int k = 0; k < n; k++) {
                if (i_j.toleft(p[k] - p[j]) == 0) res++;
            }
            return res;
        };

        if (n <= 100) {
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    int cnt = cnt_in_line(i, j);
                    if (cnt * 3 >= 2 * n) {
                        cout << n - (n - cnt) * 3 << endl;
                        goto END;
                    }
                }
                if (i == n - 1) cout << n % 3 << endl;
            }
        } else {
            for (int _ = 0; _ < 1000; _++) {
                int i = rand() % n, j = i;
                while (j == i) j = rand() % n;
                int cnt = cnt_in_line(i, j);
                if (cnt * 3 > n || cnt * 2 >= n) {
                    if (cnt * 3 >= 2 * n) cout << n - (n - cnt) * 2 << endl;
                    else cout << n % 3 << endl;
                    goto END;
                }
                if (_ == 14) cout << n % 3 << endl;
            }
        }
        END: ;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3664kb

input:

3
0 0
0 1
0 2
3
0 0
0 1
1 0
6
0 0
0 1
0 2
0 3
1 1
1 2

output:

3
0
0

result:

ok 3 lines

Test #2:

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

input:

1
0 0
2
0 0
1 1
3
0 0
0 1
0 2
3
0 0
0 1
1 0
4
3 0
0 2
3 3
3 1
4
2 3
1 1
0 3
0 2
4
0 0
0 3
0 2
0 1
5
8 6
9 2
2 3
7 4
1 5
5
2 2
4 2
6 2
7 2
0 4
5
3 7
5 4
4 4
9 4
9 9
5
5 4
5 9
5 5
4 3
1 0
5
3 2
1 2
7 2
6 2
5 2
6
7 2
7 9
0 3
8 8
4 4
3 8
6
2 8
2 5
3 5
3 8
2 0
0 2
6
2 3
8 4
2 9
2 2
2 6
4 9
6
2 1
7 6
6 5
...

output:

1
2
3
0
1
1
4
2
2
2
2
5
0
0
0
0
0
0
0
3
0
6

result:

ok 22 lines

Test #3:

score: 0
Accepted
time: 4ms
memory: 3672kb

input:

7
0 1
0 0
7 7
6 2
6 9
4 4
3 5
7
3 7
3 2
9 1
0 6
1 8
5 0
9 5
7
3 7
2 3
4 5
6 7
7 7
5 8
4 7
7
1 6
5 7
7 2
3 5
0 8
8 8
3 8
7
1 8
3 4
8 8
1 9
7 8
1 7
0 0
7
6 9
2 7
4 5
2 1
4 6
2 3
7 6
7
3 1
1 9
5 7
6 6
5 2
5 1
5 3
7
6 4
1 6
7 3
5 4
2 3
0 0
3 2
7
2 9
4 9
8 9
8 0
1 7
2 6
6 2
7
3 5
4 0
4 1
4 3
0 8
4 7
4 6
...

output:

1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1

result:

ok 21 lines

Test #4:

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

input:

8
3 2
4 4
3 9
7 9
9 3
9 1
4 2
5 3
8
0 6
0 2
1 6
9 9
5 5
8 4
6 8
0 9
8
1 8
8 1
9 0
1 3
6 4
3 6
4 0
1 6
8
5 3
1 0
0 1
7 1
3 7
8 8
6 4
6 2
8
3 3
7 8
0 8
6 3
0 4
2 3
5 3
5 4
8
6 2
9 7
3 2
6 5
2 2
1 5
4 7
2 5
8
1 1
1 0
1 5
2 8
8 9
8 8
0 0
1 4
8
8 0
3 3
8 2
5 5
3 0
0 0
6 2
8 9
8
3 9
3 5
3 1
6 5
6 2
1 1
8 ...

output:

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2

result:

ok 57 lines

Test #5:

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

input:

9
14 16
8 14
18 19
0 10
5 9
0 5
1 2
12 9
15 11
9
16 12
3 9
10 14
17 14
6 10
2 19
17 17
0 13
7 2
9
17 1
14 13
5 14
9 2
13 0
1 18
17 13
11 3
5 13
9
13 0
13 3
5 4
6 14
3 5
17 14
5 17
19 17
5 6
9
3 18
18 9
14 14
6 4
17 10
16 15
8 14
10 14
18 16
9
17 10
19 19
1 16
18 17
9 13
10 15
19 3
6 16
17 16
9
13 2
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 86 lines

Test #6:

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

input:

17
87310293 387438180
71556828 322852519
229718797 511837973
310313906 370688881
259858018 463145945
252802375 462493335
347775953 550587600
68053426 326582700
386313403 373022317
211296869 571386994
138237064 241008526
196230475 364801713
327348063 266915603
238976759 498766159
215667837 559919342
...

output:

2
1
0
1
2
2
2
1
2
1
2
4
1
1
2
1
12
1
0
4
2
1
1
6
2
1
0
0
2
2
2
3
1
2
0
2
1
0
13
1
0
1
4
2
1
2
2
8
1
0
1
0
0
0
2
3
1
9
0
2
0
2
20
7
2
8
1
0
8
0
3
7
0
8
14
1
0
2
2
3
0
0
1
1
15
1
1
1
0
2
2
2
4
1
1
1
1
1
0
2
2
11
2
0
0
2
1
8
2
5
0
2
1
0
0
1
8
2
1
0
0
1
1
0
1
9
1
2
7
1
4
7
0
0
1
0
0
0
2
2
2
18
1
2
0
0
0...

result:

ok 10000 lines

Test #7:

score: -100
Wrong Answer
time: 141ms
memory: 3584kb

input:

42
287252230 499236706
148773418 586949728
167210058 575271888
85809270 626831466
382208482 439091044
366321992 449153609
390308514 433960452
343740886 463456570
180682406 566738450
384441280 437676781
259245916 516976015
185132890 563919496
240132841 463148835
99194724 618353067
157153022 581642054...

output:

30
118
1
65
2
6
81
79
1
0
1
0
85
0
0
0
3
4
2
1
0
2
2
138
2
135
2
2
2
2
1
3
0
2
1
0
13
0
0
1
1
2
0
1
110
2
1
0
2
80
55
92
4
1
0
1
125
0
88
1
2
1
1
0
2
73
1
2
0
78
25
67
0
0
0
2
95
2
31
1
1
0
1
1
0
0
2
0
1
19
0
2
2
70
2
2
2
0
2
1
2
1
0
1
1
133
2
24
2
0
0
126
2
1
20
1
1
2
0
47
42
1
0
39
0
73
68
1
132
0...

result:

wrong answer 2nd lines differ - expected: '116', found: '118'