QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#356847 | #2838. 2D Geometry | mendicillin2# | AC ✓ | 31ms | 5528kb | C++17 | 1.3kb | 2024-03-18 13:42:22 | 2024-03-18 13:42:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
const int N=2e5+5;
int n;
int x[N],y[N];
inline bool check(int i,int j,int k)
{
return 1LL*(y[j]-y[i])*(x[k]-x[j])==1LL*(y[k]-y[j])*(x[j]-x[i]);
}
inline int random(int l,int r)
{
return 1LL*rand()*rand()%(r-l+1)+l;
}
int main()
{
srand(time(0));
while(cin>>n)
{
for(int i=1;i<=n;i++) x[i]=read(), y[i]=read();
if(n<=20)
{
int c1=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
int cnt=2;
for(int k=1;k<=n;k++)
{
if(k==i || k==j) continue;
if(check(i,j,k)) cnt++;
}
c1=max(c1,cnt);
}
int c2=n-c1;
if(c1>=c2*2) printf("%d\n",n-3*c2);
else printf("%d\n",n%3);
continue;
}
int c1=0;
for(int i=1;i<=50;i++)
{
int p1=random(1,n);
int p2=random(1,n);
if(p1==p2) continue;
int cnt=2;
for(int k=1;k<=n;k++)
{
if(k==p1 || k==p2) continue;
if(check(p1,p2,k)) cnt++;
}
c1=max(c1,cnt);
}
int c2=n-c1;
if(c1>=c2*2) printf("%d\n",n-3*c2);
else printf("%d\n",n%3);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3788kb
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: 0ms
memory: 3972kb
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: 1ms
memory: 3804kb
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: 0ms
memory: 3840kb
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: 1ms
memory: 3852kb
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: 21ms
memory: 3972kb
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: 0
Accepted
time: 18ms
memory: 3868kb
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 116 1 38 2 6 81 79 1 0 1 0 70 0 0 0 3 4 2 1 0 2 2 123 2 126 2 2 2 1 3 0 2 1 0 13 0 0 1 1 2 0 1 83 2 1 0 2 27 18 64 4 1 0 1 105 0 88 1 2 1 1 0 2 26 1 2 0 78 25 31 0 0 0 2 55 2 31 1 1 0 1 1 0 0 2 0 1 19 0 2 2 52 2 2 2 0 2 1 2 1 0 1 1 125 2 24 2 0 0 89 2 1 20 1 1 2 0 6 42 1 0 39 0 22 68 1 122 0 2 1 ...
result:
ok 1000 lines
Test #8:
score: 0
Accepted
time: 9ms
memory: 3808kb
input:
897 350467692 235711852 389244234 222063368 420837716 381703650 283369806 495010048 184447118 330280428 310297010 390950504 214233834 528051332 354440638 220358496 265847546 562724408 282462038 498518096 427605198 245483822 352161478 229166256 336628126 289194528 276162282 426888360 260597130 417944...
output:
0 2 142 1 113 1 1037 843 0 2 0 0 0 2 266 1 0 34 0 0 2 2 2 483 1 336 0 257 1 1 2 2 1 2 1469 1 2 1 199 1353 1 1 0 0 1 0 0 2 0 582 177 0 1 483 0 1 1 37 2 2 1 1 2 0 2 0 2 1 0 685 797 2 160 98 1 0 2 391 12 0 0 711 1 1 1 0 622 1 102 0 2 1 0 1 1 2 1 0 1 1
result:
ok 100 lines
Test #9:
score: 0
Accepted
time: 29ms
memory: 3992kb
input:
20000 484231306 551517006 420281290 551091920 359676382 608733140 81227614 520320566 563828247 414564665 609175198 674071338 280942605 683616695 602064645 378198095 684292446 299991380 120008991 471514239 482864858 491568800 790812451 579371035 534625299 749120999 301947770 663638720 376253692 59296...
output:
4316 17147 2351 14579 8450 19169 12743 14672 2894 2720
result:
ok 10 lines
Test #10:
score: 0
Accepted
time: 24ms
memory: 5448kb
input:
200000 147648030 393318930 193701587 354316868 36770429 487219496 94180290 602586130 269963274 576506160 136037810 403151450 262181052 599365328 168214029 375901896 54406410 472283850 214489917 384804834 104307628 430023262 71647492 457682638 21519941 500134904 78059629 452252296 137445999 401958876...
output:
61964
result:
ok single line: '61964'
Test #11:
score: 0
Accepted
time: 25ms
memory: 5440kb
input:
200000 245596321 552966885 102410400 523825221 171777446 630033172 281818017 511169189 312133225 476187231 217594046 421887338 167721461 642829870 226226873 575318083 140500315 361360403 315519265 472279941 191569901 615310180 207708147 619645058 220483597 581945484 149900007 485305015 327777217 458...
output:
32879
result:
ok single line: '32879'
Test #12:
score: 0
Accepted
time: 31ms
memory: 5392kb
input:
200000 423197455 146020025 369800451 167801113 399195519 155810617 408198824 100388377 498967500 115112785 393235397 158241801 439421057 139402281 465760145 128658345 382423186 162652193 457699534 149531017 482101950 121992385 400995549 116394107 366277425 169238185 458035627 131809241 452748103 142...
output:
26369
result:
ok single line: '26369'
Test #13:
score: 0
Accepted
time: 28ms
memory: 5400kb
input:
200000 512797601 268680975 435691406 13794312 493541783 56401215 208415324 47480472 343608209 38950137 371503460 37190016 360463976 37886580 446696216 32445540 346838780 38746296 199048394 48071502 210605336 195606078 352888844 38364552 430337822 33477714 418507562 34224174 268851635 43667091 230229...
output:
19859
result:
ok single line: '19859'
Test #14:
score: 0
Accepted
time: 28ms
memory: 5336kb
input:
200000 617102012 294541096 578058979 350743997 565892776 368257388 686320436 194900368 653596116 242007408 579868187 348139621 700949072 173842276 593234522 328898626 548531407 393249281 645596137 253523471 664411720 226438220 676751816 208674508 621839470 287721470 645382600 253830860 646582732 252...
output:
182609
result:
ok single line: '182609'
Test #15:
score: 0
Accepted
time: 24ms
memory: 5348kb
input:
200000 48553770 498737215 54695938 482343046 54601826 482594242 59266218 470144431 52102418 489265456 56237498 478228441 61685386 463687387 50559770 493382965 50314018 494038906 63918778 457726201 43357754 512605993 69251202 443493334 57286194 475429348 44637378 509190526 53217754 486288493 53205514...
output:
176099
result:
ok single line: '176099'
Test #16:
score: 0
Accepted
time: 29ms
memory: 5344kb
input:
200000 515654909 247443381 570431717 156974238 573082517 152596188 614090684 363943800 582457325 137112795 618087461 78266214 600284726 303412500 449495453 356712057 473759861 316637064 571768397 154766583 493974749 283250241 505747685 263806110 592476221 120565629 446897669 361002546 408212909 4248...
output:
169589
result:
ok single line: '169589'
Test #17:
score: 0
Accepted
time: 28ms
memory: 5472kb
input:
200000 154765608 436574441 199069626 410909957 17535537 516069239 60971127 490907819 209817132 404684129 200498559 410082203 105625272 452221589 159600141 433773887 202039593 409189511 160603374 433192733 231235518 392276861 61403922 490657109 75765447 491203349 110708496 462095897 216980244 4005346...
output:
132341
result:
ok single line: '132341'
Test #18:
score: 0
Accepted
time: 28ms
memory: 5524kb
input:
200000 396797982 580862536 576831402 410818548 318665487 654659729 385894257 591161251 424884432 554334506 332841537 641270259 316487157 656717191 489142752 493641658 601893595 493651365 504592169 526626435 580292097 407549875 592437132 396078726 672296352 320650618 376222182 600296656 401227092 576...
output:
125831
result:
ok single line: '125831'
Test #19:
score: 0
Accepted
time: 28ms
memory: 5528kb
input:
200000 161032781 486326277 301074263 375364447 204065414 452229382 224373107 436138587 204760997 451678237 104631793 623873183 303012416 373828752 288392363 385412947 202722926 453293102 200870600 454760792 285015647 388088487 255050495 411831367 264710516 404177252 68980121 559264177 201322744 6081...
output:
88583
result:
ok single line: '88583'