QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#88343 | #1898. Race | Zuqa | AC ✓ | 823ms | 3532kb | C++20 | 2.6kb | 2023-03-16 03:20:43 | 2023-03-16 03:20:44 |
Judging History
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,我给组数据试试?
詳細信息
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"