QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311009 | #5419. Triangles | yz_ly | WA | 0ms | 3836kb | C++14 | 2.8kb | 2024-01-21 20:51:59 | 2024-01-21 20:52:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void work(int k){
if(k<0){
putchar('-');
k=-k;
}
if(k>9)
work(k/10);
putchar(k%10+'0');
}
/*
要求分成若干个锐角三角形
令在正方形边上的点的个数为x,中间点的个数为y,最后有k个三角形
易得180k=360+180x+360y
k=2+x+2y
又因为x个点至少被分成3个角,y个点至少被分成5个角,这样计算k个三角形,三角形中有3个角
所以3k>=2*4+3x+5y
乱搞一下发现k>=8
因为一个三角形很容易被分成四个三角形
所以我们只需要在8,9,10的基础上分就能够构造出所有的k<=50
8,9,10就靠自己去乱搞一下就行了
*/
int n;
struct node{
double x,y,l,r,p,q;
};
queue<node> ans,ans1;
int main(){
n=read();
if(n<8){
printf("No");
return 0;
}
puts("Yes");
int now=n;
if(n%3==2){
ans.emplace(node{0,0,9,4,0,20});
ans.emplace(node{0,20,9,4,10,20});
ans.emplace(node{10,20,9,4,11,4});
ans.emplace(node{10,20,11,4,20,20});
ans.emplace(node{20,0,20,20,11,4});
ans.emplace(node{0,0,10,0,9,4});
ans.emplace(node{10,0,11,4,9,4});
ans.emplace(node{10,0,20,0,11,4});
now-=8;
}
else if(n%3==1){
ans.emplace(node{0,0,10,8,0,20});
ans.emplace(node{20,0,10,8,20,20});
ans.emplace(node{0,20,10,8,20,20});
ans.emplace(node{0,0,8,0,5,4});
ans.emplace(node{10,3,5,4,8,0});
ans.emplace(node{10,3,8,0,12,0});
ans.emplace(node{10,3,12,0,15,4});
ans.emplace(node{10,3,15,4,10,8});
ans.emplace(node{20,0,15,4,12,0});
now-=10;
}
else{
ans.emplace(node{0,0,20,0,16,12});
ans.emplace(node{0,0,16,12,0,20});
ans.emplace(node{0,20,12,14,13,20});
ans.emplace(node{20,0,20,13,16,12});
ans.emplace(node{16,16,16,12,20,13});
ans.emplace(node{16,16,20,13,20,20});
ans.emplace(node{16,16,20,20,13,20});
ans.emplace(node{16,16,13,20,12,14});
ans.emplace(node{16,16,12,14,16,12});
now-=9;
}
while(now){
while(now&&!ans.empty()){
node k=ans.front();
ans.pop();
double g=(k.x+k.l)/2.0,g1=(k.y+k.r)/2.0,h=(k.x+k.p)/2.0,h1=(k.y+k.q)/2.0,v=(k.l+k.p)/2.0,v1=(k.r+k.q)/2.0;
ans1.emplace(node{k.x,k.y,g,g1,h,h1});
ans1.emplace(node{g,g1,h,h1,v,v1});
ans1.emplace(node{k.l,k.r,g,g1,v,v1});
ans1.emplace(node{k.p,k.q,h,h1,v,v1});
now-=3;
}
while(!ans1.empty()){
ans.emplace(ans1.front());
ans1.pop();
}
}
while(!ans.empty()){
node k=ans.front();
ans.pop();
work(k.x*5e7);
putchar(' ');
work(k.y*5e7);
putchar(' ');
work(k.l*5e7);
putchar(' ');
work(k.r*5e7);
putchar(' ');
work(k.p*5e7);
putchar(' ');
work(k.q*5e7);
putchar('\n');
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
2
output:
No
result:
ok no solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
24
output:
Yes 800000000 800000000 1000000000 650000000 1000000000 1000000000 800000000 800000000 1000000000 1000000000 650000000 1000000000 800000000 800000000 650000000 1000000000 600000000 700000000 800000000 800000000 600000000 700000000 800000000 600000000 0 0 500000000 0 400000000 300000000 500000000 0 4...
result:
ok 24 acute triangles
Test #3:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
1
output:
No
result:
ok no solution
Test #4:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
3
output:
No
result:
ok no solution
Test #5:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
4
output:
No
result:
ok no solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
5
output:
No
result:
ok no solution
Test #7:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
6
output:
No
result:
ok no solution
Test #8:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
7
output:
No
result:
ok no solution
Test #9:
score: 0
Accepted
time: 0ms
memory: 3564kb
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: 3504kb
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: -100
Wrong Answer
time: 0ms
memory: 3560kb
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 400000000 0 600000000 0 500000000 1500000...
result:
wrong output format Unexpected end of file - int32 expected