QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#759846 | #5419. Triangles | Mitsubachi | WA | 0ms | 3800kb | C++14 | 3.7kb | 2024-11-18 12:39:49 | 2024-11-18 12:39:51 |
Judging History
answer
// g++-13 1.cpp -std=c++17 -O2 -I .
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())
random_device seed;
mt19937_64 randint(seed());
ll grr(ll mi, ll ma) { // [mi, ma)
return mi + randint() % (ma - mi);
}
ll mx = 1e9;
using P = pair<int,int>;
using T = tuple<P,P,P>;
P mid(P &a,P &b){
auto [ax,ay]=a;
auto [bx,by]=b;
return {(ll)(ax+bx)/2,(ll)(ay+by)/2};
}
vector<T> plus3(T &tr){
auto [i,j,k]=tr;
auto ni=mid(j,k),nj=mid(k,i),nk=mid(i,j);
vector<T> res;
res.emplace_back(i,nj,nk);
res.emplace_back(ni,j,nk);
res.emplace_back(ni,nj,k);
res.emplace_back(ni,nj,nk);
return res;
}
void sub_output(P &p){
cout<<p.first<<" "<<p.second<<" ";
}
ll len(P &a,P &b){
auto [ax,ay]=a;
auto [bx,by]=b;
return (ll)(ax-bx)*(ax-bx)+(ll)(ay-by)*(ay-by);
}
void is_ok(T &tr){
auto [i,j,k]=tr;
vll l={len(i,j),len(j,k),len(k,i)};
sort(all(l));
if(l[0]+l[1]<l[2]){
cerr<<"FAILED!"<<endl;
cerr<<l[0]<<" "<<l[1]<<" "<<l[2]<<endl;
}
return;
}
void output(T &tr){
is_ok(tr);
auto [i,j,k]=tr;
sub_output(i);
sub_output(j);
sub_output(k);
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// https://kennji72019.blog.fc2.com/blog-entry-9326.html
// https://ics.uci.edu/~eppstein/junkyard/acute-square/
int k;cin>>k;
if(k<=7){
cout<<"No"<<endl;
return 0;
}
cout<<"Yes"<<endl;
int md=k%3;
vector<T> ans;
auto push=[&](int ax,int ay,int bx,int by,int cx,int cy,int l=1){
ax*=l;ay*=l;bx*=l;by*=l;cx*=l;cy*=l;
ans.push_back({{ax,ay},{bx,by},{cx,cy}});
};
if(md==0){
// k = 9
int l=mx/100;
push(0,0,39,0,30,27,l);
push(0,0,30,27,0,40,l);
push(30,27,0,40,32,44,l);
push(0,40,0,100,32,44,l);
push(0,100,100,100,40,30,l);
push(100,100,40,30,100,0,l);
push(39,0,100,0,40,30,l);
push(39,0,30,27,40,30,l);
push(30,27,40,30,32,44,l);
}
else if(md==1){
// k = 10
int l=mx/100;
push(0,100,30,30,100,100,l);
push(100,0,30,30,100,100,l);
push(0,24,0,100,30,30,l);
push(24,0,100,0,30,30,l);
push(0,0,15,15,0,24,l);
push(0,0,15,15,24,0,l);
push(0,24,15,15,20,28,l);
push(24,0,15,15,28,20,l);
push(30,30,28,20,20,28,l);
push(15,15,20,28,28,20,l);
}
else{
// k = 8
int l=mx/100;
push(0,0,50,0,40,80,l);
push(100,0,50,0,60,80,l);
push(25,80,50,0,60,80,l);
push(0,100,50,100,40,80,l);
push(100,100,50,100,60,80,l);
push(40,80,50,100,60,80,l);
push(0,0,0,100,40,80,l);
push(100,0,100,100,60,80,l);
}
while(ans.size()<k){
int n=ans.size();
vector<T> nans;
rep(i,1,n)nans.emplace_back(ans[i]);
auto add=plus3(ans[0]);
rep(i,0,4)nans.emplace_back(add[i]);
ans=nans;
}
rep(i,0,k){
output(ans[i]);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
input:
2
output:
No
result:
ok no solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
24
output:
Yes 1000000000 1000000000 400000000 300000000 1000000000 0 390000000 0 1000000000 0 400000000 300000000 390000000 0 300000000 270000000 400000000 300000000 300000000 270000000 400000000 300000000 320000000 440000000 0 0 150000000 135000000 195000000 0 345000000 135000000 390000000 0 195000000 0...
result:
ok 24 acute triangles
Test #3:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
1
output:
No
result:
ok no solution
Test #4:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
3
output:
No
result:
ok no solution
Test #5:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
4
output:
No
result:
ok no solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
5
output:
No
result:
ok no solution
Test #7:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
6
output:
No
result:
ok no solution
Test #8:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
7
output:
No
result:
ok no solution
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3748kb
input:
8
output:
Yes 0 0 500000000 0 400000000 800000000 1000000000 0 500000000 0 600000000 800000000 250000000 800000000 500000000 0 600000000 800000000 0 1000000000 500000000 1000000000 400000000 800000000 1000000000 1000000000 500000000 1000000000 600000000 800000000 400000000 800000000 500000000 1000000000 ...
result:
wrong answer triangle 4 not acute