QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#893223 | #10006. Good Triangle | lgvc# | TL | 1ms | 3840kb | C++23 | 996b | 2025-02-10 16:46:03 | 2025-02-10 16:46:06 |
Judging History
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);
}
詳細信息
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...