QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#311009#5419. Trianglesyz_lyWA 0ms3836kbC++142.8kb2024-01-21 20:51:592024-01-21 20:52:00

Judging History

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

  • [2024-01-21 20:52:00]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3836kb
  • [2024-01-21 20:51:59]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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