QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#76115#5419. TrianglesAppleblue17AC ✓2ms3704kbC++141.8kb2023-02-07 19:13:282023-02-07 19:13:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-07 19:13:29]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3704kb
  • [2023-02-07 19:13:28]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
struct pnt{
	double x,y;
};
double gdis(pnt X,pnt Y){
	return sqrt((X.x-Y.x)*(X.x-Y.x)+(X.y-Y.y)*(X.y-Y.y));
}
pnt gmid(pnt X,pnt Y){
	return (pnt){(X.x+Y.x)/2,(X.y+Y.y)/2};
}
pnt A={0,0},B={0,10},C={10,10},D={10,0};
pnt E={4.5,8},F={5.5,8},G={5,10},H={5,0}; 
pnt I={4.7,10},J={5.3,10},K={5,8};
pnt L={8,6},M={8,8},N={6.5,10},O={10,6.3},P={6,7};

struct triangle{
	pnt x,y,z;
};
double glen(triangle X){
	return gdis(X.x,X.y)+gdis(X.y,X.z)+gdis(X.z,X.x);
}
bool operator <(triangle X,triangle Y){
	return glen(X)<glen(Y);
}

triangle fx8[8]={
{A,B,E},{B,G,E},{A,E,H},
{C,D,F},{C,F,G},{D,F,H},
{E,F,G},{E,F,H},
};

triangle fx9[9]={
{B,P,N},{A,B,L},{A,D,L},{D,O,L},
{M,P,N},{M,N,C},{M,C,O},{M,O,L},{M,L,P},
};

triangle fx10[10]={
{A,B,E},{B,I,E},{A,E,H},
{C,D,F},{C,F,J},{D,F,H},
{E,I,K},{J,F,K},{I,J,K},{E,F,H},
};

priority_queue <triangle> q;

int n;
int main(){
	cin>>n;
	if(n<8) return puts("No"),0;
	puts("Yes");
	int st;
	if(n%3==0){
		st=9;
		for(int i=0;i<9;i++) q.push(fx9[i]);
	}
	else if(n%3==1){
		st=10;
		for(int i=0;i<10;i++) q.push(fx10[i]);
	}
	else{
		st=8;
		for(int i=0;i<8;i++) q.push(fx8[i]);
	}
	
	for(int t=1;t<=(n-st)/3;t++){
		triangle u=q.top(); q.pop();
		pnt x=u.x,y=u.y,z=u.z;
		q.push({x,gmid(x,y),gmid(x,z)});
		q.push({y,gmid(y,x),gmid(y,z)});
		q.push({z,gmid(z,x),gmid(z,y)});
		q.push({gmid(x,y),gmid(y,z),gmid(z,x)});
	}
	
	while(q.size()){
		triangle u=q.top(); q.pop();
		pnt x=u.x,y=u.y,z=u.z;
		cout<<setprecision(0)<<fixed<<x.x*1e8<<" "<<x.y*1e8<<" "<<y.x*1e8<<" "<<y.y*1e8<<" "<<z.x*1e8<<" "<<z.y*1e8<<'\n';
//		cout<<setprecision(0)<<fixed<<"Polygon( "<<"("<<x.x*1e8<<", "<<x.y*1e8<<"), ("<<y.x*1e8<<", "<<y.y*1e8<<"), ("<<z.x*1e8<<", "<<z.y*1e8<<") )\n";
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3332kb

input:

2

output:

No

result:

ok no solution

Test #2:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

24

output:

Yes
0 1000000000 0 500000000 400000000 800000000
800000000 600000000 400000000 300000000 400000000 800000000
0 0 0 500000000 400000000 300000000
800000000 600000000 400000000 300000000 900000000 300000000
0 0 500000000 0 400000000 300000000
1000000000 0 500000000 0 900000000 300000000
500000000 0 90...

result:

ok 24 acute triangles

Test #3:

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

input:

1

output:

No

result:

ok no solution

Test #4:

score: 0
Accepted
time: 2ms
memory: 3512kb

input:

3

output:

No

result:

ok no solution

Test #5:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

4

output:

No

result:

ok no solution

Test #6:

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

input:

5

output:

No

result:

ok no solution

Test #7:

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

input:

6

output:

No

result:

ok no solution

Test #8:

score: 0
Accepted
time: 2ms
memory: 3352kb

input:

7

output:

No

result:

ok no solution

Test #9:

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

input:

8

output:

Yes
0 0 0 1000000000 450000000 800000000
1000000000 1000000000 1000000000 0 550000000 800000000
0 0 450000000 800000000 500000000 0
1000000000 0 550000000 800000000 500000000 0
450000000 800000000 550000000 800000000 500000000 0
0 1000000000 500000000 1000000000 450000000 800000000
1000000000 100000...

result:

ok 8 acute triangles

Test #10:

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

input:

9

output:

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

result:

ok 9 acute triangles

Test #11:

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

input:

10

output:

Yes
0 0 0 1000000000 450000000 800000000
1000000000 1000000000 1000000000 0 550000000 800000000
0 0 450000000 800000000 500000000 0
1000000000 0 550000000 800000000 500000000 0
450000000 800000000 550000000 800000000 500000000 0
1000000000 1000000000 550000000 800000000 530000000 1000000000
0 100000...

result:

ok 10 acute triangles

Test #12:

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

input:

11

output:

Yes
1000000000 1000000000 1000000000 0 550000000 800000000
0 0 450000000 800000000 500000000 0
1000000000 0 550000000 800000000 500000000 0
450000000 800000000 550000000 800000000 500000000 0
0 500000000 225000000 900000000 225000000 400000000
450000000 800000000 225000000 400000000 225000000 900000...

result:

ok 11 acute triangles

Test #13:

score: 0
Accepted
time: 2ms
memory: 3508kb

input:

12

output:

Yes
0 0 1000000000 0 800000000 600000000
0 1000000000 600000000 700000000 650000000 1000000000
1000000000 0 1000000000 630000000 800000000 600000000
0 500000000 400000000 800000000 400000000 300000000
0 1000000000 0 500000000 400000000 800000000
800000000 600000000 400000000 300000000 400000000 8000...

result:

ok 12 acute triangles

Test #14:

score: 0
Accepted
time: 2ms
memory: 3572kb

input:

13

output:

Yes
1000000000 1000000000 1000000000 0 550000000 800000000
0 0 450000000 800000000 500000000 0
1000000000 0 550000000 800000000 500000000 0
450000000 800000000 550000000 800000000 500000000 0
450000000 800000000 225000000 400000000 225000000 900000000
0 500000000 225000000 900000000 225000000 400000...

result:

ok 13 acute triangles

Test #15:

score: 0
Accepted
time: 2ms
memory: 3604kb

input:

14

output:

Yes
0 0 450000000 800000000 500000000 0
1000000000 0 550000000 800000000 500000000 0
450000000 800000000 550000000 800000000 500000000 0
1000000000 500000000 775000000 400000000 775000000 900000000
0 500000000 225000000 900000000 225000000 400000000
1000000000 0 1000000000 500000000 775000000 400000...

result:

ok 14 acute triangles

Test #16:

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

input:

15

output:

Yes
0 1000000000 600000000 700000000 650000000 1000000000
1000000000 0 1000000000 630000000 800000000 600000000
0 500000000 400000000 800000000 400000000 300000000
0 1000000000 0 500000000 400000000 800000000
800000000 600000000 400000000 300000000 400000000 800000000
0 0 0 500000000 400000000 30000...

result:

ok 15 acute triangles

Test #17:

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

input:

16

output:

Yes
0 0 450000000 800000000 500000000 0
1000000000 0 550000000 800000000 500000000 0
450000000 800000000 550000000 800000000 500000000 0
1000000000 0 1000000000 500000000 775000000 400000000
550000000 800000000 775000000 900000000 775000000 400000000
450000000 800000000 225000000 400000000 225000000...

result:

ok 16 acute triangles

Test #18:

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

input:

17

output:

Yes
1000000000 0 550000000 800000000 500000000 0
450000000 800000000 550000000 800000000 500000000 0
1000000000 500000000 775000000 400000000 775000000 900000000
0 500000000 225000000 900000000 225000000 400000000
550000000 800000000 775000000 900000000 775000000 400000000
1000000000 0 1000000000 50...

result:

ok 17 acute triangles

Test #19:

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

input:

18

output:

Yes
1000000000 0 1000000000 630000000 800000000 600000000
0 500000000 400000000 800000000 400000000 300000000
0 1000000000 0 500000000 400000000 800000000
800000000 600000000 400000000 300000000 400000000 800000000
0 0 0 500000000 400000000 300000000
800000000 600000000 400000000 300000000 900000000...

result:

ok 18 acute triangles

Test #20:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

19

output:

Yes
1000000000 0 550000000 800000000 500000000 0
450000000 800000000 550000000 800000000 500000000 0
1000000000 0 1000000000 500000000 775000000 400000000
550000000 800000000 775000000 900000000 775000000 400000000
450000000 800000000 225000000 400000000 225000000 900000000
1000000000 1000000000 100...

result:

ok 19 acute triangles

Test #21:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

20

output:

Yes
450000000 800000000 550000000 800000000 500000000 0
1000000000 500000000 775000000 400000000 775000000 900000000
0 500000000 225000000 900000000 225000000 400000000
550000000 800000000 775000000 900000000 775000000 400000000
1000000000 0 1000000000 500000000 775000000 400000000
450000000 8000000...

result:

ok 20 acute triangles

Test #22:

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

input:

21

output:

Yes
0 500000000 400000000 800000000 400000000 300000000
0 1000000000 0 500000000 400000000 800000000
800000000 600000000 400000000 300000000 400000000 800000000
0 0 0 500000000 400000000 300000000
800000000 600000000 400000000 300000000 900000000 300000000
0 0 500000000 0 400000000 300000000
1000000...

result:

ok 21 acute triangles

Test #23:

score: 0
Accepted
time: 2ms
memory: 3612kb

input:

22

output:

Yes
450000000 800000000 550000000 800000000 500000000 0
1000000000 0 1000000000 500000000 775000000 400000000
550000000 800000000 775000000 900000000 775000000 400000000
450000000 800000000 225000000 400000000 225000000 900000000
1000000000 1000000000 1000000000 500000000 775000000 900000000
0 50000...

result:

ok 22 acute triangles

Test #24:

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

input:

23

output:

Yes
1000000000 500000000 775000000 400000000 775000000 900000000
0 500000000 225000000 900000000 225000000 400000000
550000000 800000000 775000000 900000000 775000000 400000000
1000000000 0 1000000000 500000000 775000000 400000000
450000000 800000000 225000000 400000000 225000000 900000000
100000000...

result:

ok 23 acute triangles

Test #25:

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

input:

25

output:

Yes
1000000000 0 1000000000 500000000 775000000 400000000
550000000 800000000 775000000 900000000 775000000 400000000
450000000 800000000 225000000 400000000 225000000 900000000
1000000000 1000000000 1000000000 500000000 775000000 900000000
0 500000000 225000000 900000000 225000000 400000000
0 0 0 5...

result:

ok 25 acute triangles

Test #26:

score: 0
Accepted
time: 2ms
memory: 3572kb

input:

26

output:

Yes
0 500000000 225000000 900000000 225000000 400000000
550000000 800000000 775000000 900000000 775000000 400000000
1000000000 0 1000000000 500000000 775000000 400000000
450000000 800000000 225000000 400000000 225000000 900000000
1000000000 1000000000 1000000000 500000000 775000000 900000000
0 0 0 5...

result:

ok 26 acute triangles

Test #27:

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

input:

27

output:

Yes
800000000 600000000 400000000 300000000 400000000 800000000
0 0 0 500000000 400000000 300000000
800000000 600000000 400000000 300000000 900000000 300000000
0 0 500000000 0 400000000 300000000
1000000000 0 500000000 0 900000000 300000000
500000000 0 900000000 300000000 400000000 300000000
8000000...

result:

ok 27 acute triangles

Test #28:

score: 0
Accepted
time: 2ms
memory: 3604kb

input:

28

output:

Yes
550000000 800000000 775000000 900000000 775000000 400000000
450000000 800000000 225000000 400000000 225000000 900000000
1000000000 1000000000 1000000000 500000000 775000000 900000000
0 500000000 225000000 900000000 225000000 400000000
0 0 0 500000000 225000000 400000000
0 1000000000 0 500000000 ...

result:

ok 28 acute triangles

Test #29:

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

input:

29

output:

Yes
550000000 800000000 775000000 900000000 775000000 400000000
1000000000 0 1000000000 500000000 775000000 400000000
450000000 800000000 225000000 400000000 225000000 900000000
1000000000 1000000000 1000000000 500000000 775000000 900000000
0 0 0 500000000 225000000 400000000
0 1000000000 0 50000000...

result:

ok 29 acute triangles

Test #30:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

30

output:

Yes
0 0 0 500000000 400000000 300000000
800000000 600000000 400000000 300000000 900000000 300000000
0 0 500000000 0 400000000 300000000
1000000000 0 500000000 0 900000000 300000000
500000000 0 900000000 300000000 400000000 300000000
800000000 800000000 1000000000 1000000000 1000000000 630000000
8000...

result:

ok 30 acute triangles

Test #31:

score: 0
Accepted
time: 2ms
memory: 3552kb

input:

31

output:

Yes
450000000 800000000 225000000 400000000 225000000 900000000
1000000000 1000000000 1000000000 500000000 775000000 900000000
0 500000000 225000000 900000000 225000000 400000000
0 0 0 500000000 225000000 400000000
0 1000000000 0 500000000 225000000 900000000
1000000000 500000000 775000000 400000000...

result:

ok 31 acute triangles

Test #32:

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

input:

32

output:

Yes
1000000000 0 1000000000 500000000 775000000 400000000
450000000 800000000 225000000 400000000 225000000 900000000
1000000000 1000000000 1000000000 500000000 775000000 900000000
0 0 0 500000000 225000000 400000000
0 1000000000 0 500000000 225000000 900000000
1000000000 1000000000 550000000 800000...

result:

ok 32 acute triangles

Test #33:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

33

output:

Yes
800000000 600000000 400000000 300000000 900000000 300000000
0 0 500000000 0 400000000 300000000
1000000000 0 500000000 0 900000000 300000000
500000000 0 900000000 300000000 400000000 300000000
800000000 800000000 1000000000 1000000000 1000000000 630000000
800000000 800000000 650000000 1000000000...

result:

ok 33 acute triangles

Test #34:

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

input:

34

output:

Yes
1000000000 1000000000 1000000000 500000000 775000000 900000000
0 500000000 225000000 900000000 225000000 400000000
0 0 0 500000000 225000000 400000000
0 1000000000 0 500000000 225000000 900000000
1000000000 500000000 775000000 400000000 775000000 900000000
1000000000 1000000000 550000000 8000000...

result:

ok 34 acute triangles

Test #35:

score: 0
Accepted
time: 2ms
memory: 3612kb

input:

35

output:

Yes
450000000 800000000 225000000 400000000 225000000 900000000
1000000000 1000000000 1000000000 500000000 775000000 900000000
0 0 0 500000000 225000000 400000000
0 1000000000 0 500000000 225000000 900000000
1000000000 1000000000 550000000 800000000 500000000 1000000000
0 1000000000 500000000 100000...

result:

ok 35 acute triangles

Test #36:

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

input:

36

output:

Yes
0 0 500000000 0 400000000 300000000
1000000000 0 500000000 0 900000000 300000000
500000000 0 900000000 300000000 400000000 300000000
800000000 800000000 1000000000 1000000000 1000000000 630000000
800000000 800000000 650000000 1000000000 1000000000 1000000000
0 1000000000 300000000 850000000 3250...

result:

ok 36 acute triangles

Test #37:

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

input:

37

output:

Yes
0 500000000 225000000 900000000 225000000 400000000
0 0 0 500000000 225000000 400000000
0 1000000000 0 500000000 225000000 900000000
1000000000 500000000 775000000 400000000 775000000 900000000
1000000000 1000000000 550000000 800000000 530000000 1000000000
0 1000000000 470000000 1000000000 45000...

result:

ok 37 acute triangles

Test #38:

score: 0
Accepted
time: 2ms
memory: 3528kb

input:

38

output:

Yes
1000000000 1000000000 1000000000 500000000 775000000 900000000
0 0 0 500000000 225000000 400000000
0 1000000000 0 500000000 225000000 900000000
1000000000 1000000000 550000000 800000000 500000000 1000000000
0 1000000000 500000000 1000000000 450000000 800000000
0 0 225000000 400000000 250000000 0...

result:

ok 38 acute triangles

Test #39:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

39

output:

Yes
1000000000 0 500000000 0 900000000 300000000
500000000 0 900000000 300000000 400000000 300000000
800000000 800000000 1000000000 1000000000 1000000000 630000000
800000000 800000000 650000000 1000000000 1000000000 1000000000
0 1000000000 300000000 850000000 325000000 1000000000
300000000 850000000...

result:

ok 39 acute triangles

Test #40:

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

input:

40

output:

Yes
0 0 0 500000000 225000000 400000000
0 1000000000 0 500000000 225000000 900000000
1000000000 500000000 775000000 400000000 775000000 900000000
1000000000 1000000000 550000000 800000000 530000000 1000000000
0 1000000000 470000000 1000000000 450000000 800000000
775000000 400000000 525000000 4000000...

result:

ok 40 acute triangles

Test #41:

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

input:

41

output:

Yes
0 0 0 500000000 225000000 400000000
0 1000000000 0 500000000 225000000 900000000
1000000000 1000000000 550000000 800000000 500000000 1000000000
0 1000000000 500000000 1000000000 450000000 800000000
0 0 225000000 400000000 250000000 0
450000000 800000000 225000000 400000000 475000000 400000000
77...

result:

ok 41 acute triangles

Test #42:

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

input:

42

output:

Yes
500000000 0 900000000 300000000 400000000 300000000
800000000 800000000 1000000000 1000000000 1000000000 630000000
800000000 800000000 650000000 1000000000 1000000000 1000000000
0 1000000000 300000000 850000000 325000000 1000000000
300000000 850000000 625000000 850000000 325000000 1000000000
600...

result:

ok 42 acute triangles

Test #43:

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

input:

43

output:

Yes
0 1000000000 0 500000000 225000000 900000000
1000000000 500000000 775000000 400000000 775000000 900000000
1000000000 1000000000 550000000 800000000 530000000 1000000000
0 1000000000 470000000 1000000000 450000000 800000000
775000000 400000000 525000000 400000000 750000000 0
225000000 400000000 4...

result:

ok 43 acute triangles

Test #44:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

44

output:

Yes
0 1000000000 0 500000000 225000000 900000000
1000000000 1000000000 550000000 800000000 500000000 1000000000
0 1000000000 500000000 1000000000 450000000 800000000
0 0 225000000 400000000 250000000 0
450000000 800000000 225000000 400000000 475000000 400000000
775000000 400000000 525000000 40000000...

result:

ok 44 acute triangles

Test #45:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

45

output:

Yes
800000000 800000000 1000000000 1000000000 1000000000 630000000
800000000 800000000 650000000 1000000000 1000000000 1000000000
0 1000000000 300000000 850000000 325000000 1000000000
300000000 850000000 625000000 850000000 325000000 1000000000
600000000 700000000 300000000 850000000 625000000 85000...

result:

ok 45 acute triangles

Test #46:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

46

output:

Yes
1000000000 500000000 775000000 400000000 775000000 900000000
1000000000 1000000000 550000000 800000000 530000000 1000000000
0 1000000000 470000000 1000000000 450000000 800000000
775000000 400000000 525000000 400000000 750000000 0
225000000 400000000 475000000 400000000 250000000 0
500000000 0 75...

result:

ok 46 acute triangles

Test #47:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

47

output:

Yes
1000000000 1000000000 550000000 800000000 500000000 1000000000
0 1000000000 500000000 1000000000 450000000 800000000
0 0 225000000 400000000 250000000 0
450000000 800000000 225000000 400000000 475000000 400000000
775000000 400000000 525000000 400000000 750000000 0
225000000 400000000 475000000 4...

result:

ok 47 acute triangles

Test #48:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

48

output:

Yes
800000000 800000000 650000000 1000000000 1000000000 1000000000
0 1000000000 300000000 850000000 325000000 1000000000
300000000 850000000 625000000 850000000 325000000 1000000000
600000000 700000000 300000000 850000000 625000000 850000000
650000000 1000000000 325000000 1000000000 625000000 850000...

result:

ok 48 acute triangles

Test #49:

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

input:

49

output:

Yes
1000000000 1000000000 550000000 800000000 530000000 1000000000
0 1000000000 470000000 1000000000 450000000 800000000
775000000 400000000 525000000 400000000 750000000 0
225000000 400000000 475000000 400000000 250000000 0
500000000 0 750000000 0 525000000 400000000
550000000 800000000 775000000 4...

result:

ok 49 acute triangles

Test #50:

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

input:

50

output:

Yes
0 1000000000 500000000 1000000000 450000000 800000000
0 0 225000000 400000000 250000000 0
450000000 800000000 225000000 400000000 475000000 400000000
775000000 400000000 525000000 400000000 750000000 0
225000000 400000000 475000000 400000000 250000000 0
500000000 0 750000000 0 525000000 40000000...

result:

ok 50 acute triangles