QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310512#5419. TriangleslefyTL 1ms4064kbC++142.2kb2024-01-21 15:02:422024-01-21 15:02:42

Judging History

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

  • [2024-01-21 15:02:42]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4064kb
  • [2024-01-21 15:02:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int A[15][6]={
	0,0,9,4,0,20,
	0,20,9,4,10,20,
	10,20,9,4,11,4,
	10,20,11,4,20,20,
	20,0,20,20,11,4,
	0,0,10,0,9,4,
	10,0,11,4,9,4,
	10,0,20,0,11,4
};
int b[15][6]={
	0,0,20,0,16,12,
	0,0,16,12,0,20,
	0,20,12,14,13,20,
	20,0,20,13,16,12,
	16,16,16,12,20,13,
	16,16,20,13,20,20,
	16,16,20,20,13,20,
	16,16,13,20,12,14,
	16,16,12,14,16,12
};
int c[15][6]={
	0,0,10,8,0,20,
	20,0,10,8,20,20,
	0,20,10,8,20,20,
	0,0,8,0,5,4,
	10,3,5,4,8,0,
	10,3,10,8,5,4,
	10,3,8,0,12,0,
	10,3,12,0,15,4,
	10,3,15,4,10,8,
	20,0,15,4,12,0
};
struct node{
    int x1,y1,x2,y2,x3,y3;
};
int a[15][6];
void solve(int k){
    int r=k%3,ed;
    if(r==2)ed=8;else if(!r)ed=9;else ed=10;
    queue<node>q;
    int num=5e7;
    for(int i=0;i<ed;i++){
        q.push({a[i][0]*num,a[i][1]*num,a[i][2]*num,a[i][3]*num,a[i][4]*num,a[i][5]*num});
        //~ q.push({a[i][0],a[i][1],a[i][2],a[i][3],a[i][4],a[i][5]});
    }
    while((int)q.size()<k){
        node now=q.front();q.pop();
        int x1=now.x1,y1=now.y1,x2=now.x2,y2=now.y2,x3=now.x3,y3=now.y3;
        int x4,y4,x5,y5,x6,y6;
        x4=(x1+x2)>>1;y4=(y1+y2)>>1;
        x5=(x1+x3)>>1;y5=(y1+y3)>>1;
        x6=(x2+x3)>>1;y6=(y2+y3)>>1;
        if(x4==min(x1,x2)||y4==min(y1,y2)||
        x5==min(x1,x3)||y5==min(y1,y3)||
        x6==min(x3,x2)||y6==min(y3,y2)){q.push(now);continue;}
        q.push({x1,y1,x4,y4,x5,y5});
        q.push({x4,y4,x5,y5,x6,y6});
        q.push({x2,y2,x4,y4,x6,y6});
        q.push({x3,y3,x5,y5,x6,y6});
        //~ cout<<q.size()<<"\n";
    }
    while(k--){
        node now=q.front();q.pop();
        //~ cout<<"Polygon\n";
        //~ cout<<now.x1<<" "<<now.y1<<"\n";
        //~ cout<<now.x2<<" "<<now.y2<<"\n";
        //~ cout<<now.x3<<" "<<now.y3<<"\n";
        //~ cout<<"\n";
        printf("%d %d %d %d %d %d\n",now.x1,now.y1,now.x2,now.y2,now.x3,now.y3);
    }
}

int main(){
    int k;
     scanf("%d",&k);
     
    //~ cout<<(dis(0,5e8,5e7,27)>dis(0,5e8,5e8,5e8));
    if(k<8)printf("No\n");
    else{
        printf("Yes\n");
        if(k%3==2)swap(A,a);
        else if(!(k%3))swap(a,b);
        else swap(a,c);
        solve(k);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2

output:

No

result:

ok no solution

Test #2:

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

input:

24

output:

Yes
800000000 800000000 600000000 700000000 800000000 600000000
0 0 1000000000 0 800000000 600000000
0 0 800000000 600000000 0 1000000000
0 1000000000 600000000 700000000 650000000 1000000000
1000000000 0 1000000000 650000000 800000000 600000000
800000000 800000000 800000000 600000000 1000000000 650...

result:

ok 24 acute triangles

Test #3:

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

input:

1

output:

No

result:

ok no solution

Test #4:

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

input:

3

output:

No

result:

ok no solution

Test #5:

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

input:

4

output:

No

result:

ok no solution

Test #6:

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

input:

5

output:

No

result:

ok no solution

Test #7:

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

input:

6

output:

No

result:

ok no solution

Test #8:

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

input:

7

output:

No

result:

ok no solution

Test #9:

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

input:

8

output:

Yes
0 0 450000000 200000000 0 1000000000
0 1000000000 450000000 200000000 500000000 1000000000
500000000 1000000000 450000000 200000000 550000000 200000000
500000000 1000000000 550000000 200000000 1000000000 1000000000
1000000000 0 1000000000 1000000000 550000000 200000000
0 0 500000000 0 450000000 ...

result:

ok 8 acute triangles

Test #10:

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

input:

9

output:

Yes
0 0 1000000000 0 800000000 600000000
0 0 800000000 600000000 0 1000000000
0 1000000000 600000000 700000000 650000000 1000000000
1000000000 0 1000000000 650000000 800000000 600000000
800000000 800000000 800000000 600000000 1000000000 650000000
800000000 800000000 1000000000 650000000 1000000000 1...

result:

ok 9 acute triangles

Test #11:

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

input:

10

output:

Yes
0 0 500000000 400000000 0 1000000000
1000000000 0 500000000 400000000 1000000000 1000000000
0 1000000000 500000000 400000000 1000000000 1000000000
0 0 400000000 0 250000000 200000000
500000000 150000000 250000000 200000000 400000000 0
500000000 150000000 500000000 400000000 250000000 200000000
5...

result:

ok 10 acute triangles

Test #12:

score: -100
Time Limit Exceeded

input:

11

output:


result: