QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#549100#5419. TrianglesWuyanruAC ✓0ms3960kbC++142.9kb2024-09-06 08:26:352024-09-06 08:26:35

Judging History

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

  • [2024-09-06 08:26:35]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3960kb
  • [2024-09-06 08:26:35]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
struct node
{
    int x,y;
    node(){ x=y=0;}
    inline bool check()
    {
        if(x&1) return false;
        if(y&1) return false;
        return true;
    }
    node operator + (node b)
    {
        node ans;
        ans.x=(x+b.x)/2;
        ans.y=(y+b.y)/2;
        return ans;
    }
    inline void output()
    {
        printf("%d %d",x,y);
    }
};
struct T
{
    node a,b,c;
    T():a(),b(),c(){}
    T(node x,node y,node z){ a=x,b=y,c=z;}
    inline bool check()
    {
        return a.check()&&b.check()&&c.check();
    }
    inline void output()
    {
        a.output(),putchar(' ');
        b.output(),putchar(' ');
        c.output(),putchar('\n');
    }
};
vc<T>ans;
int n;
inline void run()
{
    for(auto &i:ans) if(i.check())
    {
        node c=i.a+i.b;
        node b=i.a+i.c;
        node a=i.c+i.b;

        auto mem=i;
        i=T(a,b,c);
        ans.push_back(T(mem.a,b,c));
        ans.push_back(T(a,mem.b,c));
        ans.push_back(T(a,b,mem.c));
        return ;
    }
    assert(0);
}
const int L=10000000;
inline void push(int x1,int y1,int x2,int y2,int x3,int y3)
{
    node a;a.x=x1*L,a.y=y1*L;
    node b;b.x=x2*L,b.y=y2*L;
    node c;c.x=x3*L,c.y=y3*L;
    ans.push_back(T(a,b,c));
}
inline void run8()
{
    push(0,0,90,48,100,0);
    push(0,0,0,50,90,48);
    push(100,0,100,50,90,48);
    push(0,100,90,52,100,100);
    push(0,100,0,50,90,52);
    push(100,100,100,50,90,52);
    push(0,50,90,48,90,52);
    push(100,50,90,48,90,52);
}
inline void run10()
{
    push(0,0,90,48,100,0);
    push(0,0,0,49,90,48);
    push(100,0,100,50,90,48);
    push(0,100,90,52,100,100);
    push(0,100,0,51,90,52);
    push(100,100,100,50,90,52);
    push(100,50,90,48,90,52);

    push(90,48,90,50,0,49);
    push(90,52,90,50,0,51);
    push(0,49,0,51,90,50);
}
inline void run9()
{
    push(40,80,100,0,100,100);
    push(40,80,0,0,100,0);
    push(40,80,39,100,100,100);
    push(39,100,40,80,20,80);
    push(39,100,0,100,20,80);
    push(30,60,20,80,40,80);
    push(0,0,0,65,30,60);
    push(0,65,30,60,20,80);
    push(0,65,20,80,0,100);
}
int main()
{
    n=read();
    if(n<=7)
    {
        printf("No\n");
        return 0;
    }
    printf("Yes\n");
    int now=-1;
    if(n%3==2) now=8,run8();
    else if(n%3==1) now=10,run10();
    else now=9,run9();

    while(now<n) run(),now+=3;

    for(auto i:ans) i.output();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2

output:

No

result:

ok no solution

Test #2:

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

input:

24

output:

Yes
812500000 593750000 793750000 618750000 793750000 587500000
400000000 800000000 0 0 1000000000 0
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 800000000
300000000 600000000 2...

result:

ok 24 acute triangles

Test #3:

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

input:

1

output:

No

result:

ok no solution

Test #4:

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

input:

3

output:

No

result:

ok no solution

Test #5:

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

input:

4

output:

No

result:

ok no solution

Test #6:

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

input:

5

output:

No

result:

ok no solution

Test #7:

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

input:

6

output:

No

result:

ok no solution

Test #8:

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

input:

7

output:

No

result:

ok no solution

Test #9:

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

input:

8

output:

Yes
0 0 900000000 480000000 1000000000 0
0 0 0 500000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900000000 520000000
0 5000...

result:

ok 8 acute triangles

Test #10:

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

input:

9

output:

Yes
400000000 800000000 1000000000 0 1000000000 1000000000
400000000 800000000 0 0 1000000000 0
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 800000000
300000000 600000000 200000...

result:

ok 9 acute triangles

Test #11:

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

input:

10

output:

Yes
0 0 900000000 480000000 1000000000 0
0 0 0 490000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900000000 520000000
100000...

result:

ok 10 acute triangles

Test #12:

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

input:

11

output:

Yes
950000000 240000000 500000000 0 450000000 240000000
0 0 0 500000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900000000 5...

result:

ok 11 acute triangles

Test #13:

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

input:

12

output:

Yes
1000000000 500000000 700000000 900000000 700000000 400000000
400000000 800000000 0 0 1000000000 0
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 800000000
300000000 600000000 ...

result:

ok 12 acute triangles

Test #14:

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

input:

13

output:

Yes
950000000 240000000 500000000 0 450000000 240000000
0 0 0 490000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900000000 5...

result:

ok 13 acute triangles

Test #15:

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

input:

14

output:

Yes
475000000 120000000 700000000 240000000 725000000 120000000
0 0 0 500000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 14 acute triangles

Test #16:

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

input:

15

output:

Yes
700000000 650000000 850000000 450000000 850000000 700000000
400000000 800000000 0 0 1000000000 0
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 800000000
300000000 600000000 2...

result:

ok 15 acute triangles

Test #17:

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

input:

16

output:

Yes
475000000 120000000 700000000 240000000 725000000 120000000
0 0 0 490000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 16 acute triangles

Test #18:

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

input:

17

output:

Yes
712500000 180000000 600000000 120000000 587500000 180000000
0 0 0 500000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 17 acute triangles

Test #19:

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

input:

18

output:

Yes
850000000 575000000 775000000 675000000 775000000 550000000
400000000 800000000 0 0 1000000000 0
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 800000000
300000000 600000000 2...

result:

ok 18 acute triangles

Test #20:

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

input:

19

output:

Yes
712500000 180000000 600000000 120000000 587500000 180000000
0 0 0 490000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 19 acute triangles

Test #21:

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

input:

20

output:

Yes
593750000 150000000 650000000 180000000 656250000 150000000
0 0 0 500000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 20 acute triangles

Test #22:

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

input:

21

output:

Yes
775000000 612500000 812500000 562500000 812500000 625000000
400000000 800000000 0 0 1000000000 0
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 800000000
300000000 600000000 2...

result:

ok 21 acute triangles

Test #23:

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

input:

22

output:

Yes
593750000 150000000 650000000 180000000 656250000 150000000
0 0 0 490000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 22 acute triangles

Test #24:

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

input:

23

output:

Yes
653125000 165000000 625000000 150000000 621875000 165000000
0 0 0 500000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 23 acute triangles

Test #25:

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

input:

25

output:

Yes
653125000 165000000 625000000 150000000 621875000 165000000
0 0 0 490000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 25 acute triangles

Test #26:

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

input:

26

output:

Yes
623437500 157500000 637500000 165000000 639062500 157500000
0 0 0 500000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 26 acute triangles

Test #27:

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

input:

27

output:

Yes
793750000 603125000 803125000 590625000 803125000 606250000
400000000 800000000 0 0 1000000000 0
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 800000000
300000000 600000000 2...

result:

ok 27 acute triangles

Test #28:

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

input:

28

output:

Yes
623437500 157500000 637500000 165000000 639062500 157500000
0 0 0 490000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 28 acute triangles

Test #29:

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

input:

29

output:

Yes
638281250 161250000 631250000 157500000 630468750 161250000
0 0 0 500000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 29 acute triangles

Test #30:

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

input:

30

output:

Yes
803125000 598437500 798437500 604687500 798437500 596875000
400000000 800000000 0 0 1000000000 0
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 800000000
300000000 600000000 2...

result:

ok 30 acute triangles

Test #31:

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

input:

31

output:

Yes
638281250 161250000 631250000 157500000 630468750 161250000
0 0 0 490000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 31 acute triangles

Test #32:

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

input:

32

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
0 0 0 500000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 32 acute triangles

Test #33:

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

input:

33

output:

Yes
798437500 600781250 800781250 597656250 800781250 601562500
400000000 800000000 0 0 1000000000 0
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 800000000
300000000 600000000 2...

result:

ok 33 acute triangles

Test #34:

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

input:

34

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
0 0 0 490000000 900000000 480000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 1000000000 500000000 900...

result:

ok 34 acute triangles

Test #35:

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

input:

35

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
450000000 490000000 450000000 240000000 0 250000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 10000000...

result:

ok 35 acute triangles

Test #36:

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

input:

36

output:

Yes
800781250 599609375 799609375 601171875 799609375 599218750
400000000 800000000 0 0 1000000000 0
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 800000000
300000000 600000000 2...

result:

ok 36 acute triangles

Test #37:

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

input:

37

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
450000000 485000000 450000000 240000000 0 245000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 10000000...

result:

ok 37 acute triangles

Test #38:

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

input:

38

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
225000000 245000000 225000000 370000000 450000000 365000000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 ...

result:

ok 38 acute triangles

Test #39:

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

input:

39

output:

Yes
800781250 599609375 799609375 601171875 799609375 599218750
500000000 0 700000000 400000000 200000000 400000000
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 800000000
300000...

result:

ok 39 acute triangles

Test #40:

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

input:

40

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
225000000 242500000 225000000 365000000 450000000 362500000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 ...

result:

ok 40 acute triangles

Test #41:

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

input:

41

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
337500000 367500000 337500000 305000000 225000000 307500000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 ...

result:

ok 41 acute triangles

Test #42:

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

input:

42

output:

Yes
800781250 599609375 799609375 601171875 799609375 599218750
450000000 400000000 350000000 200000000 600000000 200000000
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 80000000...

result:

ok 42 acute triangles

Test #43:

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

input:

43

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
337500000 363750000 337500000 302500000 225000000 303750000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 ...

result:

ok 43 acute triangles

Test #44:

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

input:

44

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
281250000 306250000 281250000 337500000 337500000 336250000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 ...

result:

ok 44 acute triangles

Test #45:

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

input:

45

output:

Yes
800781250 599609375 799609375 601171875 799609375 599218750
475000000 200000000 525000000 300000000 400000000 300000000
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 80000000...

result:

ok 45 acute triangles

Test #46:

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

input:

46

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
281250000 303125000 281250000 333750000 337500000 333125000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 ...

result:

ok 46 acute triangles

Test #47:

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

input:

47

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
309375000 336875000 309375000 321250000 281250000 321875000
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 ...

result:

ok 47 acute triangles

Test #48:

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

input:

48

output:

Yes
800781250 599609375 799609375 601171875 799609375 599218750
462500000 300000000 437500000 250000000 500000000 250000000
400000000 800000000 390000000 1000000000 1000000000 1000000000
390000000 1000000000 400000000 800000000 200000000 800000000
390000000 1000000000 0 1000000000 200000000 80000000...

result:

ok 48 acute triangles

Test #49:

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

input:

49

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
309375000 333437500 309375000 318125000 281250000 318437500
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 510000000 900000000 520000000
1000000000 1000000000 ...

result:

ok 49 acute triangles

Test #50:

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

input:

50

output:

Yes
630859375 159375000 634375000 161250000 634765625 159375000
295312500 321562500 295312500 329375000 309375000 329062500
1000000000 0 1000000000 500000000 900000000 480000000
0 1000000000 900000000 520000000 1000000000 1000000000
0 1000000000 0 500000000 900000000 520000000
1000000000 1000000000 ...

result:

ok 50 acute triangles