QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#893223#10006. Good Trianglelgvc#TL 1ms3840kbC++23996b2025-02-10 16:46:032025-02-10 16:46:06

Judging History

This is the latest submission verdict.

  • [2025-02-10 16:46:06]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 3840kb
  • [2025-02-10 16:46:03]
  • Submitted

answer

#include <bits/stdc++.h>
int N;
struct n_t{
    int x,y;
} f[500009];
bool cmp(n_t a,n_t b) {
    return a.x<b.x;
}
signed main(void) {
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        scanf("%d %d",&f[i].x,&f[i].y);
    }
    long long ans=1ll*N*(N-1)*(N-2)/6;
    std::sort(f+1,f+N+1,cmp);
    for(int i=1;i<=N;i++) {
        int c1=0,c2=0;
        for(int j=1;j<i;j++) {
            if(f[i].x-f[j].x>abs(f[i].y-f[j].y)) c1++;
        }
        for(int j=i+1;j<=N;j++) {
            if(f[j].x-f[i].x>abs(f[i].y-f[j].y)) c2++;
        }
        ans-=1ll*c1*c2;
    }
    for(int i=1;i<=N;i++) std::swap(f[i].x,f[i].y);
    std::sort(f+1,f+N+1,cmp);
    for(int i=1;i<=N;i++) {
        int c1=0,c2=0;
        for(int j=1;j<i;j++) {
            if(f[i].x-f[j].x>abs(f[i].y-f[j].y)) c1++;
        }
        for(int j=i+1;j<=N;j++) {
            if(f[j].x-f[i].x>abs(f[i].y-f[j].y)) c2++;
        }
        ans-=1ll*c1*c2;
    }
    printf("%lld",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 -1
1 5
5 7
1 3
4 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

10
-2 -1
-2 2
-1 -2
-1 -1
-1 1
0 1
1 -1
1 2
2 -1
2 1

output:

108

result:

ok 1 number(s): "108"

Test #3:

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

input:

8
-5353885 177168259
393803106 -221988732
517220368 -345405994
143143400 28670974
-179553118 351367492
447166616 -275352242
-72145562 243959936
-274698525 446512899

output:

56

result:

ok 1 number(s): "56"

Test #4:

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

input:

8
-324947127 116858935
372954148 -81124978
54845173 -262933365
122995467 -331083659
-350010483 641839653
-599969164 391880972
-74988446 366817616
-73250266 365079436

output:

56

result:

ok 1 number(s): "56"

Test #5:

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

input:

10
157433098 -150486510
741495015 -58558849
860039937 59986073
613972809 306053201
403500226 -396553638
68842013 -239077595
314909141 -485144723
-24746679 -332666287
221320449 -578733415
495427887 187508279

output:

120

result:

ok 1 number(s): "120"

Test #6:

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

input:

9
179264487 -544344907
139756831 -583852563
481689324 -241920070
223597013 -500012381
828224017 104614623
14865396 -708743998
89252586 -634356808
475703232 -247906162
301875222 -421734172

output:

84

result:

ok 1 number(s): "84"

Test #7:

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

input:

10
-623065093 198755267
-368090840 -393092046
225795796 409211766
-93406399 728413961
372178992 555594962
52976797 874797157
-303862898 -120446928
-472299428 -288883458
-791501623 30318737
476387580 451386374

output:

114

result:

ok 1 number(s): "114"

Test #8:

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

input:

8
-436280563 40679439
68302509 -89073311
-52148970 471776818
589381280 336967420
34530786 385097062
-248865402 228094600
-333757066 143202936
-119112652 -276488472

output:

49

result:

ok 1 number(s): "49"

Test #9:

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

input:

10
-477236362 165824920
188776620 -500188062
-8340601 577345567
662040674 -93035708
-159868135 425818033
78314899 664001067
497779358 -191185324
-123585922 462100246
-60356350 802672316
184430545 648794743

output:

106

result:

ok 1 number(s): "106"

Test #10:

score: -100
Time Limit Exceeded

input:

499998
-12023827 330263227
-664373810 24735206
305768212 -67930490
368765325 213424915
33206371 919185805
-647540955 191952141
355341003 -524613427
539454004 145694368
-404535204 559105834
-740702365 168088895
-149191340 -73936930
195872405 -752246739
34365000 -408325744
576078603 -102167279
4304638...

output:


result: