QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88343#1898. RaceZuqaAC ✓823ms3532kbC++202.6kb2023-03-16 03:20:432023-03-16 03:20:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-16 03:20:44]
  • 评测
  • 测评结果:AC
  • 用时:823ms
  • 内存:3532kb
  • [2023-03-16 03:20:43]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;

template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937_64 for long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

void doWork()
{
    int n;
    cin >> n;
    vector <pair<ll, ll>> v(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> v[i].first >> v[i].second;

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            int anyT = 0;
            map<pair<ll, ll>, int> mp;

            ll y1 = j - i;
            ll x1 = v[j].first - v[i].first;
            ll v1 = v[j].second - v[i].second;
            for(int k = j + 1; k <= n; k++)
            {
                ll y2 = k - i;
                ll x2 = v[k].first - v[i].first;
                ll v2 = v[k].second - v[i].second;
                ll A = x1 * y2, B = x2 * y1, C = v2 * y1, D = v1 * y2;

                // ax * by - ay * bx == 0
                // (x1 + t * v1) * y2 - (x2 + t * v2) * y1 == 0
                // x1y2 + tv1y2 - x2y1 - tv2y1 = 0
                // x1y2 - x2y1 = tv2y1 - tv1y2
                // x1y2 - x2y1 = t(v2y1 - v1y2)
                // A - B = t*(C - D)
                // t = (A - B) / (C - D)

                if(C == D && A == B) // any T will work when A == B
                {
                    anyT++;
                    continue;
                }
                else if(C == D) // !0 == 0
                    continue;

                ll a = A - B, b = C - D, g = __gcd(a, b);
                a /= g, b /= g;
                if(b < 0)
                    a *= -1, b *= -1;
                if(a >= 0)
                    mp[{a, b}]++;
            }
            ans = max(ans, anyT); // 2 is i and j
            for(auto &it: mp)
                ans = max(ans, it.second + anyT);
        }
    }
    cout << ans + 2;
}

signed main()
{
    FIO
    int T = 1;
//    cin >> T;
    for(int i = 1; i <= T; i++)
        doWork();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 1
0 3
3 2

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3388kb

input:

10
6648 37
13620 78
11242 64
28 43
99 86
-78 59
16180 93
17372 100
73 76
-83 43

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 2ms
memory: 3344kb

input:

10
-32705 188
-32879 189
-7153 42
-44777 257
-35326 203
-42500 244
-59 170
-34448 198
-31997 184
-13971 81

output:

9

result:

ok 1 number(s): "9"

Test #4:

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

input:

10
-4225 87
-8905 221
-3925 79
-185 4
-6075 141
-2495 39
-1470 10
-1740 18
-5685 131
-6270 148

output:

9

result:

ok 1 number(s): "9"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3508kb

input:

10
-24855 193
-16590 134
-32220 252
-330 18
-18390 154
-29025 235
-16710 146
-5205 63
-28935 241
241 236

output:

9

result:

ok 1 number(s): "9"

Test #6:

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

input:

10
-35544 180
107 154
-27781 141
-279 207
-42 179
-295 279
-21608 110
-26781 136
-29964 152
-55 92

output:

5

result:

ok 1 number(s): "5"

Test #7:

score: 0
Accepted
time: 2ms
memory: 3428kb

input:

10
-125 147
-12890 260
-5387 133
200 180
-12388 252
240 82
-13666 274
-5691 139
-187 42
294 196

output:

5

result:

ok 1 number(s): "5"

Test #8:

score: 0
Accepted
time: 2ms
memory: 3364kb

input:

10
-293 272
-100830 285
-78410 145
-56464 8
297 28
-83514 183
-297 283
93 16
-56702 19
177 199

output:

5

result:

ok 1 number(s): "5"

Test #9:

score: 0
Accepted
time: 2ms
memory: 3500kb

input:

10
-287 7
-31 159
141 265
-209 193
6 38
-191 63
-22 215
-12509 55
-140 98
139 161

output:

3

result:

ok 1 number(s): "3"

Test #10:

score: 0
Accepted
time: 3ms
memory: 3304kb

input:

10
-96 212
-16 135
-202 218
79 224
-296 137
194 294
-253 122
-138 129
-46933 297
-266 114

output:

3

result:

ok 1 number(s): "3"

Test #11:

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

input:

10
174 144
-163 265
132 165
-21951 279
-75 65
-72 247
190 104
178 3
-270 115
142 73

output:

3

result:

ok 1 number(s): "3"

Test #12:

score: 0
Accepted
time: 317ms
memory: 3436kb

input:

239
-86 11
508 13
2850 91
2642 84
96 88
3126 100
2618 83
1510 46
2352 74
1004 29
1486 45
-14 46
4 11
2422 76
2154 67
-96 76
-77 97
55 72
3002 95
2104 65
99 2
2198 68
2680 84
-63 34
75 40
1006 28
1308 38
-85 45
34 47
88 46
-22 59
1 99
64 5
66 27
1564 46
2916 91
2078 63
-20 92
44 23
1904 57
15 80
2118...

output:

5

result:

ok 1 number(s): "5"

Test #13:

score: 0
Accepted
time: 166ms
memory: 3368kb

input:

239
-8077 281
-7824 272
-4099 139
-3734 126
-7261 252
-2388 78
-4375 149
-71 57
40 81
-4624 158
-4063 138
-5518 190
-3697 125
-1400 43
-1315 40
-1258 38
104 52
-892 25
-2963 99
-3522 119
-833 23
-23 196
-7635 266
-3210 108
-1893 61
-268 3
-295 4
-854 24
-4269 146
-768 21
-5415 187
-5386 186
-2221 73...

output:

216

result:

ok 1 number(s): "216"

Test #14:

score: 0
Accepted
time: 165ms
memory: 3520kb

input:

239
-19532 242
-9414 109
-23540 295
-20642 257
130 177
-21382 267
-10124 119
-13078 158
-4632 47
-23774 299
-14416 176
-4906 51
-10444 124
-10358 123
-17492 217
-17862 222
-22032 277
-10850 130
-19428 243
141 37
-10440 125
-22970 290
-8748 103
-7370 85
-2952 27
-17762 222
-15700 195
-13030 160
-1332...

output:

216

result:

ok 1 number(s): "216"

Test #15:

score: 0
Accepted
time: 158ms
memory: 3364kb

input:

239
27010 134
27780 132
53460 24
28615 131
42310 74
17230 182
45260 64
25585 149
60665 1
50390 46
15675 195
59685 9
29670 138
17750 190
-6390 294
34800 120
12540 216
-85 271
-51 156
19785 189
58860 24
-3350 290
2590 266
-113 257
63115 11
670 278
127 257
30645 153
51155 67
44640 96
-650 290
67330 2
6...

output:

216

result:

ok 1 number(s): "216"

Test #16:

score: 0
Accepted
time: 373ms
memory: 3376kb

input:

239
-55416 264
184 153
-186 259
20 16
219 276
85 188
179 200
-269 233
-12997 63
-58783 280
-56883 271
-20379 98
2 278
6 280
118 139
-48016 229
-4127 21
-6025 30
-29234 140
154 84
-113 242
-58349 278
13 248
-21633 104
177 170
-140 122
-102 22
-56655 270
28 147
227 136
-20993 101
48 300
73 46
-47365 2...

output:

119

result:

ok 1 number(s): "119"

Test #17:

score: 0
Accepted
time: 378ms
memory: 3520kb

input:

239
20 2
-1970 12
27 251
-176 240
195 218
-1130 8
142 14
-31510 160
-51300 259
151 79
-151 129
-29270 149
-59 176
-77 299
-41840 212
-231 298
104 178
-290 251
-44600 226
-27390 140
155 224
-67 18
-56960 288
184 96
53 135
-146 93
-1920 13
-240 52
-15700 82
185 215
66 178
-28270 145
-170 244
91 44
-17...

output:

119

result:

ok 1 number(s): "119"

Test #18:

score: 0
Accepted
time: 391ms
memory: 3312kb

input:

239
102 116
-150 291
-230 81
-41431 109
77 64
-38241 99
-18257 23
-258 218
101 298
279 131
-77663 257
-237 281
-80171 269
-41 232
-18965 35
-2 127
-17329 31
-70383 237
-23204 56
-80143 277
-46691 149
-57528 192
-60595 205
-208 287
-49894 166
-72127 253
103 267
-54951 189
203 99
-230 21
202 123
29 25...

output:

119

result:

ok 1 number(s): "119"

Test #19:

score: 0
Accepted
time: 397ms
memory: 3436kb

input:

239
152 73
-120 174
290 185
-251 155
-140 279
-37 165
10 202
-188 284
29 141
-35561 228
-198 268
-90 100
-14013 89
-235 156
69 26
-30750 197
-208 208
-19 57
-82 282
-9 295
-15 202
-144 195
-29813 191
43 23
-167 288
-267 154
-78 185
-137 60
-60 292
-209 52
71 279
179 279
71 206
-146 117
-73 99
-183 3...

output:

23

result:

ok 1 number(s): "23"

Test #20:

score: 0
Accepted
time: 407ms
memory: 3364kb

input:

239
-121 78
32 252
-104 51
107 287
152 55
213 157
5 243
-194 60
49 247
36 149
-238 179
-138 168
-75 76
-65 117
-91 197
249 285
-272 120
-136 29
-107 29
-287 165
-8298 31
-216 83
-258 217
242 53
139 117
-176 25
224 77
188 224
108 54
-83 260
53 226
-29 78
-207 215
-295 203
-231 272
158 223
-108 149
21...

output:

23

result:

ok 1 number(s): "23"

Test #21:

score: 0
Accepted
time: 407ms
memory: 3312kb

input:

239
64 78
-78 139
-48726 169
242 259
105 118
19 36
-214 141
43 50
173 294
151 17
-49 104
271 4
254 14
37 19
41 182
94 149
61 174
268 285
-161 203
-98 20
127 136
-33 239
-117 120
-175 283
295 97
157 259
-299 258
-214 3
-255 104
-28 147
142 46
18 263
-140 291
33 144
101 247
20 27
-245 142
-275 132
62 ...

output:

23

result:

ok 1 number(s): "23"

Test #22:

score: 0
Accepted
time: 658ms
memory: 3532kb

input:

300
66 72
3811 43
3813 43
509 5
80 33
8430 96
4604 52
1561 17
2868 32
-22 90
-27 64
81 16
-50 11
11 25
-63 93
96 12
7930 90
5496 62
4193 47
367 3
4458 50
-46 48
-23 54
8031 91
3161 35
-21 83
5 54
-52 32
-16 20
735 7
-91 97
-97 36
-10 94
4136 46
0 10
-43 64
6404 72
-83 76
8322 94
-46 23
4846 54
7632 ...

output:

7

result:

ok 1 number(s): "7"

Test #23:

score: 0
Accepted
time: 336ms
memory: 3288kb

input:

300
-13477 69
-45261 232
-9965 51
-1579 8
-33753 173
-35312 181
-32386 166
-55005 282
-47594 244
15 21
-57732 296
-24776 127
-27895 143
-13854 71
-31013 159
-52072 267
-4686 24
-41540 213
-24184 124
-52068 267
-44852 230
-35686 183
-54990 282
-7214 37
-50893 261
-35487 182
-53036 272
-17740 91
-2144...

output:

270

result:

ok 1 number(s): "270"

Test #24:

score: 0
Accepted
time: 336ms
memory: 3452kb

input:

300
-13515 127
-25055 237
-3310 30
-26715 253
-28175 267
-16300 154
-3480 32
-4415 41
-19735 187
-3765 35
-12470 118
-3220 30
-187 238
-25040 238
-13375 127
-23235 221
-15245 145
-1165 11
-26040 248
-3980 38
-11 283
207 98
-16970 162
-6040 58
-10335 99
-26390 252
-24700 236
-2955 29
-27095 259
-1333...

output:

270

result:

ok 1 number(s): "270"

Test #25:

score: 0
Accepted
time: 318ms
memory: 3344kb

input:

300
34132 244
65164 88
74329 43
65567 89
68625 75
35632 244
62724 108
28352 284
33577 259
66776 92
82048 16
78014 38
-216 173
74477 59
62366 122
58332 144
80499 33
-78 20
40714 238
72140 80
63378 126
38659 253
88406 2
77674 58
35422 274
57983 161
55919 173
50309 203
75037 79
36331 277
64211 137
6037...

output:

270

result:

ok 1 number(s): "270"

Test #26:

score: 0
Accepted
time: 750ms
memory: 3372kb

input:

300
-23449 256
30 271
74 61
-15074 164
-15710 171
-2 66
-11795 128
-1966 20
219 281
57 10
-152 273
-12609 137
192 51
-18431 201
-66 244
-24526 268
-261 205
73 200
-72 251
-25705 281
-2590 27
70 29
173 173
38 237
-3132 33
51 41
-35 266
124 254
-22784 249
-12864 140
-1306 13
-105 203
231 189
-119 246
...

output:

150

result:

ok 1 number(s): "150"

Test #27:

score: 0
Accepted
time: 766ms
memory: 3528kb

input:

300
-16834 78
-38337 179
-48977 229
-40447 189
-53430 250
-239 250
175 233
-14208 66
47 55
-25051 117
-17799 83
-31208 146
197 82
250 7
-34799 163
-36067 169
-135 131
-16451 77
-159 186
-40074 188
-12800 60
-4057 19
-96 220
-200 169
-212 201
137 34
-58109 273
-15073 71
-45096 212
-268 106
-26332 124...

output:

150

result:

ok 1 number(s): "150"

Test #28:

score: 0
Accepted
time: 733ms
memory: 3360kb

input:

300
62502 59
55032 94
204 130
-27 124
-272 172
-65 79
81 107
62 241
76446 7
253 144
40416 172
96 230
67212 54
66846 57
47166 147
42360 170
147 106
137 55
71232 44
-271 7
59622 99
-35 88
181 279
65184 78
59490 105
81 259
18798 291
69048 66
-239 243
19254 293
-148 299
252 155
8 274
28668 256
58938 121...

output:

150

result:

ok 1 number(s): "150"

Test #29:

score: 0
Accepted
time: 823ms
memory: 3380kb

input:

300
-253 282
-93 221
41 262
-146 181
290 256
190 245
-17534 276
55 80
102 57
19 101
212 84
92 175
-146 59
-223 84
-160 257
62 149
-1 243
122 293
129 197
-11889 188
-177 131
-294 62
51 235
165 66
82 242
-286 22
109 286
2 8
-166 159
36 237
146 233
-287 167
-163 4
-230 221
-82 17
-261 188
171 217
137 4...

output:

30

result:

ok 1 number(s): "30"

Test #30:

score: 0
Accepted
time: 813ms
memory: 3520kb

input:

300
-125 3
-286 41
-209 62
-152 124
290 294
-66638 277
-68 88
-264 172
-222 122
-79 120
-63172 263
-134 143
246 41
-21174 91
-34340 145
158 261
-204 14
-297 126
40 125
129 16
220 244
294 268
-8884 41
-285 157
-179 188
-198 132
-148 19
-300 245
110 58
113 207
-117 121
-237 152
81 288
237 189
190 145
...

output:

30

result:

ok 1 number(s): "30"

Test #31:

score: 0
Accepted
time: 806ms
memory: 3372kb

input:

300
180 142
97 196
132 212
-224 245
-187 33
-226 14
154 43
-57 46
-255 26
155 248
-69 157
63 3
83 242
32644 182
-179 116
-171 191
-124 123
235 100
-79 7
137 231
-123 131
-270 149
86 13
105 96
43 103
-62 82
21 26
-216 254
-156 210
242 88
-95 60
32766 273
268 59
114 148
31 144
127 11
138 127
179 83
19...

output:

30

result:

ok 1 number(s): "30"