QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #76147 | #5419. Triangles | AFewSuns | WA | 2ms | 3568kb | C++14 | 3.9kb | 2023-02-07 21:53:11 | 2023-02-07 21:53:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 8e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
ll n,l=1,r=0,lim=1e7;
struct point{
ll x,y;
};
point operator+(const point &x,const point &y){
return (point){x.x+y.x,x.y+y.y};
}
point operator/(const point &x,const ll &y){
return (point){x.x/y,x.y/y};
}
point operator*(const point &x,const ll &y){
return (point){x.x*y,x.y*y};
}
struct tri{
point x,y,z;
il void print(){
pf("%lld %lld %lld %lld %lld %lld\n",x.x,x.y,y.x,y.y,z.x,z.y);
}
}q[55];
void solve1(){
n-=8;
q[++r]=(tri){(point){0,0},(point){0,100},(point){25,25}};
q[++r]=(tri){(point){0,100},(point){50,100},(point){25,25}};
q[++r]=(tri){(point){0,0},(point){50,0},(point){25,25}};
q[++r]=(tri){(point){50,100},(point){75,25},(point){25,25}};
q[++r]=(tri){(point){50,0},(point){75,25},(point){25,25}};
q[++r]=(tri){(point){50,100},(point){75,25},(point){100,100}};
q[++r]=(tri){(point){50,0},(point){75,25},(point){100,0}};
q[++r]=(tri){(point){100,100},(point){75,25},(point){100,0}};
}
void solve2(){
n-=9;
q[++r]=(tri){(point){0,0},(point){0,100},(point){70,50}};
q[++r]=(tri){(point){0,0},(point){100,0},(point){70,50}};
q[++r]=(tri){(point){100,0},(point){100,60},(point){70,50}};
q[++r]=(tri){(point){0,100},(point){42,70},(point){55,100}};
q[++r]=(tri){(point){42,70},(point){70,75},(point){55,100}};
q[++r]=(tri){(point){42,70},(point){70,75},(point){70,50}};
q[++r]=(tri){(point){100,60},(point){70,75},(point){70,50}};
q[++r]=(tri){(point){100,60},(point){70,75},(point){100,100}};
q[++r]=(tri){(point){55,100},(point){70,75},(point){100,100}};
}
void solve3(){
n-=10;
q[++r]=(tri){(point){0,0},(point){0,100},(point){50,30}};
q[++r]=(tri){(point){100,100},(point){0,100},(point){50,30}};
q[++r]=(tri){(point){100,100},(point){100,0},(point){50,30}};
q[++r]=(tri){(point){0,0},(point){40,0},(point){30,18}};
q[++r]=(tri){(point){100,0},(point){60,0},(point){70,18}};
q[++r]=(tri){(point){30,18},(point){50,14},(point){50,30}};
q[++r]=(tri){(point){30,18},(point){50,14},(point){40,0}};
q[++r]=(tri){(point){60,0},(point){50,14},(point){40,0}};
q[++r]=(tri){(point){60,0},(point){50,14},(point){70,18}};
q[++r]=(tri){(point){50,30},(point){50,14},(point){70,18}};
}
int main(){
n=read();
if(n<=7){
pf("No");
return 0;
}
pf("Yes\n");
if(n%3==2) solve1();
else if(n%3==0) solve2();
else solve3();
fr(i,l,r){
q[i].x=q[i].x*lim;
q[i].y=q[i].y*lim;
q[i].z=q[i].z*lim;
}
while(n){
tri u=q[l];
l++;
point p1=(u.x+u.y)/2,p2=(u.y+u.z)/2,p3=(u.z+u.x)/2;
q[++r]=(tri){u.x,p1,p3};
q[++r]=(tri){p1,u.y,p2};
q[++r]=(tri){p3,p2,u.z};
q[++r]=(tri){p1,p2,p3};
n-=3;
}
fr(i,l,r) q[i].print();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3416kb
input:
2
output:
No
result:
ok no solution
Test #2:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
24
output:
Yes 420000000 700000000 700000000 750000000 700000000 500000000 1000000000 600000000 700000000 750000000 700000000 500000000 1000000000 600000000 700000000 750000000 1000000000 1000000000 550000000 1000000000 700000000 750000000 1000000000 1000000000 0 0 0 500000000 350000000 250000000 0 500000000 0...
result:
ok 24 acute triangles
Test #3:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
1
output:
No
result:
ok no solution
Test #4:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
3
output:
No
result:
ok no solution
Test #5:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
4
output:
No
result:
ok no solution
Test #6:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
5
output:
No
result:
ok no solution
Test #7:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
6
output:
No
result:
ok no solution
Test #8:
score: 0
Accepted
time: 0ms
memory: 3356kb
input:
7
output:
No
result:
ok no solution
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3540kb
input:
8
output:
Yes 0 0 0 1000000000 250000000 250000000 0 1000000000 500000000 1000000000 250000000 250000000 0 0 500000000 0 250000000 250000000 500000000 1000000000 750000000 250000000 250000000 250000000 500000000 0 750000000 250000000 250000000 250000000 500000000 1000000000 750000000 250000000 1000000000 1000...
result:
wrong answer triangle 1 not acute