QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#76115 | #5419. Triangles | Appleblue17 | AC ✓ | 2ms | 3704kb | C++14 | 1.8kb | 2023-02-07 19:13:28 | 2023-02-07 19:13:29 |
Judging History
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