QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #227516 | #5419. Triangles | Okimoto | WA | 0ms | 4072kb | C++20 | 2.4kb | 2023-10-27 17:09:22 | 2023-10-27 17:09:22 |
Judging History
answer
#include <cstdio>
#include <queue>
struct Pt
{
int x, y;
Pt()
{
x = y = 0;
}
Pt(int a, int b)
{
x = a, y = b;
}
Pt mid(Pt a)
{
return Pt((x + a.x) / 2, (y + a.y) / 2);
}
};
struct Trg
{
Pt vt[3];
Trg()
{
vt[0] = vt[1] = vt[2] = Pt();
}
Trg(Pt a, Pt b, Pt c)
{
vt[0] = a;
vt[1] = b;
vt[2] = c;
}
void print()
{
for(int i = 0; i <= 2; i++)
{
printf("%d %d ", vt[i].x, vt[i].y);
}
putchar('\n');
}
};
std::queue<Trg> q;
int main()
{
int n;
scanf("%d", &n);
int L = 1000000000;
if(n < 8)
{
printf("No\n");
return 0;
}
printf("Yes\n");
if(n % 3 == 2)
{
Pt A = Pt(0, 0);
Pt B = Pt(L, 0);
Pt C = Pt(L, L);
Pt D = Pt(L, 0);
Pt E = Pt(450000000, 800000000);
Pt F = Pt(550000000, 800000000);
Pt G = Pt(500000000, L);
Pt H = Pt(500000000, 0);
q.push(Trg(A, D, E));
q.push(Trg(C, F, B));
q.push(Trg(A, E, H));
q.push(Trg(B, F, H));
q.push(Trg(D, E, G));
q.push(Trg(C, F, G));
q.push(Trg(H, E, F));
q.push(Trg(G, E, F));
n -= 8;
}
else if(n % 3 == 0)
{
Pt A = Pt(0, 0);
Pt B = Pt(L, 0);
Pt C = Pt(L, L);
Pt D = Pt(0, L);
Pt E = Pt(600000000, 500000000);
Pt F = Pt(L, 400000000);
Pt G = Pt(300000000, 250000000);
Pt H = Pt(500000000, 0);
Pt I = Pt(650000000, 250000000);
q.push(Trg(A, D, E));
q.push(Trg(C, D, E));
q.push(Trg(C, E, F));
q.push(Trg(B, F, I));
q.push(Trg(A, G, H));
q.push(Trg(B, H, I));
q.push(Trg(E, F, I));
q.push(Trg(E, G, I));
q.push(Trg(G, H, I));
n -= 9;
}
else
{
Pt A = Pt(0, 0);
Pt B = Pt(L, 0);
Pt C = Pt(L, L);
Pt D = Pt(0, L);
Pt E = Pt(300000000, 500000000);
Pt F = Pt(700000000, 500000000);
Pt G = Pt(650000000, 750000000);
Pt H = Pt(350000000, 250000000);
Pt I = Pt(0, 400000000);
Pt J = Pt(L, 600000000);
q.push(Trg(A, B, F));
q.push(Trg(C, D, E));
q.push(Trg(D, E, I));
q.push(Trg(B, F, J));
q.push(Trg(A, H, I));
q.push(Trg(C, G, J));
q.push(Trg(E, F, G));
q.push(Trg(E, F, H));
q.push(Trg(E, H, I));
q.push(Trg(F, G, J));
n -= 10;
}
for(; n; n -= 3)
{
Trg i = q.front();
q.pop();
Pt a = i.vt[1].mid(i.vt[2]);
Pt b = i.vt[0].mid(i.vt[2]);
Pt c = i.vt[0].mid(i.vt[1]);
q.push(Trg(i.vt[0], b, c));
q.push(Trg(i.vt[1], a, c));
q.push(Trg(i.vt[2], a, b));
q.push(Trg(a, b, c));
}
while(!q.empty())
{
q.front().print();
q.pop();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
2
output:
No
result:
ok no solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 4072kb
input:
24
output:
Yes 1000000000 0 500000000 0 650000000 250000000 600000000 500000000 1000000000 400000000 650000000 250000000 600000000 500000000 300000000 250000000 650000000 250000000 300000000 250000000 500000000 0 650000000 250000000 0 0 300000000 250000000 0 500000000 0 1000000000 300000000 750000000 0 50...
result:
ok 24 acute triangles
Test #3:
score: 0
Accepted
time: 0ms
memory: 3988kb
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: 3664kb
input:
4
output:
No
result:
ok no solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3956kb
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: 3732kb
input:
7
output:
No
result:
ok no solution
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 4052kb
input:
8
output:
Yes 0 0 1000000000 0 450000000 800000000 1000000000 1000000000 550000000 800000000 1000000000 0 0 0 450000000 800000000 500000000 0 1000000000 0 550000000 800000000 500000000 0 1000000000 0 450000000 800000000 500000000 1000000000 1000000000 1000000000 550000000 800000000 500000000 1000000000 ...
result:
wrong answer triangle 5 not acute