QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#733130#5419. TrianglesPorNPtreeAC ✓0ms3716kbC++232.2kb2024-11-10 17:21:112024-11-10 17:21:11

Judging History

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

  • [2024-11-10 17:21:11]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3716kb
  • [2024-11-10 17:21:11]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define LD double
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=55;
int n,cnt;
struct comp{LL x,y;};
inline LD p2(LD x){return x*x;}
inline LD dis(comp A,comp B){return sqrtl(p2(A.x-B.x)+p2(A.y-B.y));}
inline bool chk(LD a,LD b,LD c)
{
	// LD cs=(a*a+b*b-c*c)/2/a/b;
	// printf("%.10f\n",a*a+b*b-c*c);
	if(a*a+b*b-c*c<=1e-10) assert(0);
	return a*a+b*b>c*c;
}
inline bool chk(comp A,comp B,comp C)
{
	LD a=dis(B,C),b=dis(A,C),c=dis(A,B);
	return chk(a,b,c)&&chk(b,c,a)&&chk(c,a,b);
}
vector<array<comp,3>>g;
inline bool operator==(comp A,comp B){return A.x==B.x&&A.y==B.y;}
inline comp MID(comp A,comp B){return {(A.x+B.x)>>1,(A.y+B.y)>>1};}
inline void add()
{
	for(auto i:g)
	{
		comp A=i[0],B=i[1],C=i[2];
		if((A.x&1)==(B.x&1)&&(A.x&1)==(C.x&1)&&(A.y&1)==(B.y&1)&&(A.y&1)==(C.y&1))
		{
			comp D=MID(B,C),E=MID(C,A),F=MID(A,B);
			for(int j=0;j<g.size();j++) if(g[j]==i) swap(g[j],g.back()),g.pop_back();
			g.push_back({A,E,F});g.push_back({B,D,F});g.push_back({C,D,E});
			g.push_back({D,E,F});
			return;
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
	if(n<8) return cout<<"No",0;
	if(n%3==2)
	{
		LL d=1e9/20;
		comp A={d*0,d*20},B={d*10,d*20},C={d*20,d*20},
		D={d*9,d*4},E={d*11,d*4},
		F={d*0,d*0},G={d*10,d*0},H={d*20,d*0};
		g={{A,B,D},{B,C,E},{B,D,E},{A,D,F},{C,E,H},{D,F,G},{D,E,G},{E,G,H}};
		
	}
	if(n%3==1)
	{
		LL d=1e9/40;
		comp A={d*0,d*40},B1={d*19,d*40},B2={d*21,d*40},C={d*40,d*40},
		D={d*18,d*8},E={d*22,d*8},I=MID(D,E),
		F={d*0,d*0},G={d*20,d*0},H={d*40,d*0};
		g={{A,B1,D},{B1,B2,I},{B2,C,E},{B1,D,I},{B2,I,E},{A,D,F},{C,E,H},{D,F,G},{D,E,G},{E,G,H}};
	}
	if(n%3==0)
	{
		LL d=1e9/20;
		comp A={d*0,d*0},B={d*20,d*0},C={d*20,d*20},D={d*0,d*20},
		E={d*20,d*13},F={d*13,d*20},G={d*12,d*14},H={d*16,d*12},I={d*16,d*16};
		g={{D,F,G},{F,C,I},{F,G,I},{C,I,E},{I,G,H},{I,E,H},{A,D,H},{B,E,H},{A,B,H}};
	}
	while(g.size()!=n) add();
	cout<<"Yes\n";
	for(auto i:g)
	{
		comp A=i[0],B=i[1],C=i[2];
		cout<<A.x<<" "<<A.y<<" "<<B.x<<" "<<B.y<<" "<<C.x<<" "<<C.y<<"\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2

output:

No

result:

ok no solution

Test #2:

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

input:

24

output:

Yes
450000000 150000000 700000000 150000000 650000000 300000000
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 800000000...

result:

ok 24 acute triangles

Test #3:

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

input:

1

output:

No

result:

ok no solution

Test #4:

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

input:

3

output:

No

result:

ok no solution

Test #5:

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

input:

4

output:

No

result:

ok no solution

Test #6:

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

input:

5

output:

No

result:

ok no solution

Test #7:

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

input:

6

output:

No

result:

ok no solution

Test #8:

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

input:

7

output:

No

result:

ok no solution

Test #9:

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

input:

8

output:

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

result:

ok 8 acute triangles

Test #10:

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

input:

9

output:

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

result:

ok 9 acute triangles

Test #11:

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

input:

10

output:

Yes
0 1000000000 475000000 1000000000 450000000 200000000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000 20000...

result:

ok 10 acute triangles

Test #12:

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

input:

11

output:

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

result:

ok 11 acute triangles

Test #13:

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

input:

12

output:

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

result:

ok 12 acute triangles

Test #14:

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

input:

13

output:

Yes
550000000 200000000 500000000 0 1000000000 0
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000 200000000
0 10...

result:

ok 13 acute triangles

Test #15:

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

input:

14

output:

Yes
475000000 600000000 225000000 600000000 250000000 1000000000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000...

result:

ok 14 acute triangles

Test #16:

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

input:

15

output:

Yes
625000000 850000000 300000000 850000000 325000000 1000000000
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 80000000...

result:

ok 15 acute triangles

Test #17:

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

input:

16

output:

Yes
462500000 600000000 225000000 600000000 237500000 1000000000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 55000000...

result:

ok 16 acute triangles

Test #18:

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

input:

17

output:

Yes
750000000 0 775000000 100000000 525000000 100000000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 0 0 5000...

result:

ok 17 acute triangles

Test #19:

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

input:

18

output:

Yes
900000000 300000000 400000000 300000000 500000000 0
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 800000000 6000000...

result:

ok 18 acute triangles

Test #20:

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

input:

19

output:

Yes
750000000 0 775000000 100000000 525000000 100000000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000 2000000...

result:

ok 19 acute triangles

Test #21:

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

input:

20

output:

Yes
237500000 800000000 362500000 800000000 350000000 600000000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 ...

result:

ok 20 acute triangles

Test #22:

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

input:

21

output:

Yes
312500000 925000000 475000000 925000000 462500000 850000000
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 800000000...

result:

ok 21 acute triangles

Test #23:

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

input:

22

output:

Yes
231250000 800000000 350000000 800000000 343750000 600000000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000...

result:

ok 22 acute triangles

Test #24:

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

input:

23

output:

Yes
650000000 100000000 637500000 50000000 762500000 50000000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 0 ...

result:

ok 23 acute triangles

Test #25:

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

input:

25

output:

Yes
650000000 100000000 637500000 50000000 762500000 50000000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000 2...

result:

ok 25 acute triangles

Test #26:

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

input:

26

output:

Yes
356250000 700000000 293750000 700000000 300000000 800000000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 ...

result:

ok 26 acute triangles

Test #27:

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

input:

27

output:

Yes
468750000 887500000 387500000 887500000 393750000 925000000
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 800000000...

result:

ok 27 acute triangles

Test #28:

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

input:

28

output:

Yes
346875000 700000000 287500000 700000000 290625000 800000000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000...

result:

ok 28 acute triangles

Test #29:

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

input:

29

output:

Yes
700000000 50000000 706250000 75000000 643750000 75000000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 0 0...

result:

ok 29 acute triangles

Test #30:

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

input:

30

output:

Yes
675000000 225000000 550000000 225000000 575000000 150000000
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 800000000...

result:

ok 30 acute triangles

Test #31:

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

input:

31

output:

Yes
700000000 50000000 706250000 75000000 643750000 75000000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000 20...

result:

ok 31 acute triangles

Test #32:

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

input:

32

output:

Yes
296875000 750000000 328125000 750000000 325000000 700000000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 ...

result:

ok 32 acute triangles

Test #33:

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

input:

33

output:

Yes
390625000 906250000 431250000 906250000 428125000 887500000
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 800000000...

result:

ok 33 acute triangles

Test #34:

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

input:

34

output:

Yes
289062500 750000000 318750000 750000000 317187500 700000000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000...

result:

ok 34 acute triangles

Test #35:

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

input:

35

output:

Yes
675000000 75000000 671875000 62500000 703125000 62500000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 0 0...

result:

ok 35 acute triangles

Test #36:

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

input:

36

output:

Yes
562500000 187500000 625000000 187500000 612500000 225000000
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 800000000...

result:

ok 36 acute triangles

Test #37:

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

input:

37

output:

Yes
675000000 75000000 671875000 62500000 703125000 62500000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000 20...

result:

ok 37 acute triangles

Test #38:

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

input:

38

output:

Yes
326562500 725000000 310937500 725000000 312500000 750000000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 ...

result:

ok 38 acute triangles

Test #39:

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

input:

39

output:

Yes
429687500 896875000 409375000 896875000 410937500 906250000
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 800000000...

result:

ok 39 acute triangles

Test #40:

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

input:

40

output:

Yes
317968750 725000000 303125000 725000000 303906250 750000000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000...

result:

ok 40 acute triangles

Test #41:

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

input:

41

output:

Yes
687500000 62500000 689062500 68750000 673437500 68750000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 0 0...

result:

ok 41 acute triangles

Test #42:

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

input:

42

output:

Yes
618750000 206250000 587500000 206250000 593750000 187500000
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 800000000...

result:

ok 42 acute triangles

Test #43:

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

input:

43

output:

Yes
687500000 62500000 689062500 68750000 673437500 68750000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000 20...

result:

ok 43 acute triangles

Test #44:

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

input:

44

output:

Yes
311718750 737500000 319531250 737500000 318750000 725000000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 ...

result:

ok 44 acute triangles

Test #45:

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

input:

45

output:

Yes
410156250 901562500 420312500 901562500 419531250 896875000
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 800000000...

result:

ok 45 acute triangles

Test #46:

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

input:

46

output:

Yes
303515625 737500000 310937500 737500000 310546875 725000000
475000000 1000000000 525000000 1000000000 500000000 200000000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000...

result:

ok 46 acute triangles

Test #47:

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

input:

47

output:

Yes
681250000 68750000 680468750 65625000 688281250 65625000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 0 0...

result:

ok 47 acute triangles

Test #48:

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

input:

48

output:

Yes
590625000 196875000 606250000 196875000 603125000 206250000
650000000 1000000000 1000000000 1000000000 800000000 800000000
650000000 1000000000 600000000 700000000 800000000 800000000
1000000000 1000000000 800000000 800000000 1000000000 650000000
800000000 800000000 600000000 700000000 800000000...

result:

ok 48 acute triangles

Test #49:

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

input:

49

output:

Yes
303515625 737500000 310937500 737500000 310546875 725000000
681250000 68750000 680468750 65625000 688281250 65625000
525000000 1000000000 1000000000 1000000000 550000000 200000000
475000000 1000000000 450000000 200000000 500000000 200000000
525000000 1000000000 500000000 200000000 550000000 2000...

result:

ok 49 acute triangles

Test #50:

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

input:

50

output:

Yes
319140625 731250000 315234375 731250000 315625000 737500000
500000000 1000000000 1000000000 1000000000 550000000 200000000
500000000 1000000000 450000000 200000000 550000000 200000000
0 1000000000 450000000 200000000 0 0
1000000000 1000000000 550000000 200000000 1000000000 0
450000000 200000000 ...

result:

ok 50 acute triangles