QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#310512 | #5419. Triangles | lefy | TL | 1ms | 4064kb | C++14 | 2.2kb | 2024-01-21 15:02:42 | 2024-01-21 15:02:42 |
Judging History
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;
}
詳細信息
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