QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#733130 | #5419. Triangles | PorNPtree | AC ✓ | 0ms | 3716kb | C++23 | 2.2kb | 2024-11-10 17:21:11 | 2024-11-10 17:21:11 |
Judging History
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