QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#733094 | #5419. Triangles | PorNPtree | TL | 0ms | 3716kb | C++23 | 3.3kb | 2024-11-10 17:10:21 | 2024-11-10 17:10:22 |
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==24)
{
cout<<R"(Yes
0 0 500000000 0 400000000 300000000
1000000000 0 500000000 0 600000000 300000000
0 0 0 500000000 300000000 400000000
0 1000000000 0 500000000 300000000 600000000
0 1000000000 500000000 1000000000 400000000 700000000
1000000000 1000000000 500000000 1000000000 600000000 700000000
1000000000 1000000000 1000000000 500000000 700000000 600000000
1000000000 0 1000000000 500000000 700000000 400000000
0 0 400000000 300000000 300000000 400000000
0 500000000 300000000 400000000 300000000 600000000
0 1000000000 300000000 600000000 400000000 700000000
500000000 1000000000 400000000 700000000 600000000 700000000
1000000000 1000000000 600000000 700000000 700000000 600000000
1000000000 500000000 700000000 600000000 700000000 400000000
1000000000 0 700000000 400000000 600000000 300000000
500000000 0 400000000 300000000 600000000 300000000
500000000 500000000 400000000 300000000 300000000 400000000
500000000 500000000 300000000 400000000 300000000 600000000
500000000 500000000 300000000 600000000 400000000 700000000
500000000 500000000 400000000 700000000 600000000 700000000
500000000 500000000 600000000 700000000 700000000 600000000
500000000 500000000 700000000 600000000 700000000 400000000
500000000 500000000 700000000 400000000 600000000 300000000
500000000 500000000 600000000 300000000 400000000 300000000
)";
return 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}};
}
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: 3644kb
input:
2
output:
No
result:
ok no solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
24
output:
Yes 0 0 500000000 0 400000000 300000000 1000000000 0 500000000 0 600000000 300000000 0 0 0 500000000 300000000 400000000 0 1000000000 0 500000000 300000000 600000000 0 1000000000 500000000 1000000000 400000000 700000000 1000000000 1000000000 500000000 1000000000 600000000 700000000 1000000000 100000...
result:
ok 24 acute triangles
Test #3:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
1
output:
No
result:
ok no solution
Test #4:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
3
output:
No
result:
ok no solution
Test #5:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
4
output:
No
result:
ok no solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
5
output:
No
result:
ok no solution
Test #7:
score: 0
Accepted
time: 0ms
memory: 3712kb
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: 3644kb
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: -100
Time Limit Exceeded
input:
9