QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#310936 | #5419. Triangles | qL | AC ✓ | 0ms | 3796kb | C++20 | 18.1kb | 2024-01-21 19:52:09 | 2024-01-21 19:52:09 |
Judging History
answer
#include<cstdio>
#include<cstdint>
#include<utility>
#include<initializer_list>
#include<limits>
#include<string>
#include<array>
#include<vector>
#include<queue>
#include<tuple>
/**
* Author: Cracker
* Version: 0x02
*/
namespace Default_Source{
#ifndef _linux_
#define likely(x) __builtin_expect(!!(x),1)
#define unlikely(x) __builtin_expect(!!(x),0)
#endif
namespace{
template<typename T>
constexpr T Inf{std::numeric_limits<T>::max()};
template<typename T>
constexpr T abs(const T&x){return x<T(0)?-x:x;}
template<typename T>
constexpr const T&min(const T&lhs,const T&rhs){return lhs<rhs?lhs:rhs;}
template<typename T>
constexpr T min(const std::initializer_list<T>&L){
T ret=*L.begin();
for(const T&it:L) ret=min(ret,it);
return ret;
}
template<typename T>
constexpr const T&max(const T&lhs,const T&rhs){return lhs<rhs?rhs:lhs;}
template<typename T>
constexpr T max(const std::initializer_list<T>&L){
T ret=*L.begin();
for(const T&it:L) ret=max(ret,it);
return ret;
}
template<typename T>
constexpr void swap(T&x,T&y){
T tmp=std::move(x);
x=std::move(y),y=std::move(tmp);
}
}
namespace Bit{
template<typename T>
typename std::enable_if<std::is_signed<T>::value,T>::type bswap(T value){
size_t n{(sizeof(T)<<3)-1};
T ret{};
for(size_t i=0,j=n-1;i<n;++i,--j) if((value>>i)&1) ret|=1<<j;
return ret;
}
template<typename T>
typename std::enable_if<std::is_unsigned<T>::value,T>::type bswap(T value){
size_t n{sizeof(T)<<3};
T ret{};
for(size_t i=0,j=n-1;i<n;++i,--j) if((value>>i)&1) ret|=1<<j;
return ret;
}
}
namespace IO{
namespace Flush{
struct Input_Flush_Base{char getc(){return getchar();}};
template<size_t BUFSIZE>
class Fast_Input_Flush_Base{
protected:
char buf[BUFSIZE],*cur=buf;
public:
Fast_Input_Flush_Base(){std::fread(buf,1,BUFSIZE,stdin);}
char getc(){return*cur++;}
};
template<size_t BUFSIZE>
class Fast_Input_Flush_Safer{
protected:
char buf[BUFSIZE],*cur,*nil;
bool reload(){return (nil=(cur=buf)+std::fread(buf,1,BUFSIZE,stdin))!=buf;}
public:
Fast_Input_Flush_Safer(){reload();}
char getc(){return (cur!=nil||reload())?*cur++:EOF;}
};
struct Output_Flush_Base{void putc(char ch){putchar(ch);}};
template<size_t BUFSIZE>
class Fast_Output_Flush_Base{
char buf[BUFSIZE],*cur=buf;
public:
~Fast_Output_Flush_Base(){std::fwrite(buf,1,cur-buf,stdout);}
void putc(char ch){*cur++=ch;}
};
template<size_t BUFSIZE>
class Fast_Output_Flush_Safer{
char buf[BUFSIZE],*cur=buf;
bool freeze(){return likely(cur!=buf)&&(fwrite(buf,1,cur-buf,stdout),cur=buf);}
public:
~Fast_Output_Flush_Safer(){freeze();}
void putc(char ch){cur-buf==BUFSIZE&&freeze(),*cur++=ch;}
};
}
template<typename _Input_Flush=Flush::Input_Flush_Base>
class InStream{
static _Input_Flush Input;
public:
template<typename T>
typename std::enable_if<std::is_integral<T>::value,InStream>::type&operator>>(T&x){
x=0;bool sign=false;char Ch=Input.getc();
for(;!isdigit(Ch);Ch=Input.getc()) if(Ch=='-') sign=true;
for(;isdigit(Ch);Ch=Input.getc()) x=x*10+(sign?-(Ch&15):(Ch&15));
return *this;
}
InStream&operator>>(char*str){
while(isspace(*str=Input.getc()));
while(!isspace(*++str=Input.getc()));
return *str='\0',*this;
}
template<typename ...Args>
InStream&read(Args&&...args){return std::initializer_list<InStream>{*this>>args...},*this;}
template<typename T>
T read(){
static T x;
return read(x),x;
}
};
template<typename _Input_Flush>
_Input_Flush InStream<_Input_Flush>::Input;
template<typename _Output_Flush=Flush::Output_Flush_Base>
class OutStream{
static _Output_Flush Output;
public:
template<typename T>
typename std::enable_if<std::is_integral<T>::value,OutStream>::type&operator<<(T x){
static char sta[114];
int top=0;
if(x<0){
Output.putc('-');
do sta[top++]=(-(x%10))|48,x/=10;
while(x);
}
else
do sta[top++]=(x%10)|48,x/=10;
while(x);
while(top) Output.putc(sta[--top]);
return *this;
}
OutStream&operator<<(char Ch){return Output.putc(Ch),*this;}
OutStream&operator<<(const char*Str){while(*Str) Output.putc(*Str++);return *this;}
OutStream&operator<<(char*Str){return *this<<(static_cast<const char*>(Str));}
template<typename ...Args>
OutStream&write(Args...args){return std::initializer_list<OutStream>{*this<<args...},*this;}
template<typename ...Args>
OutStream&writeln(Args...args){return write(args...),Output.putc('\n'),*this;}
};
template<typename _Output_Flush>
_Output_Flush OutStream<_Output_Flush>::Output;
}
namespace ModTool{
template<typename _Tp,_Tp mod,_Tp phi=mod-1>
struct Moder{
static_assert(std::is_integral<_Tp>::value,"Only integers can be modulus.");
template<typename T>
constexpr _Tp norm(T x)const{return x<0?x%mod+mod:x%mod;}
template<typename T>
constexpr _Tp unorm(T x)const{return x%mod;}
template<typename T,typename...Args>
constexpr void plus(T&x,Args...args)const{x=norm(x),void(std::initializer_list<T>{(x=unorm(x+norm(args)))...});}
template<typename T,typename...Args>
constexpr void mult(T&x,Args...args)const{x=norm(x),void(std::initializer_list<T>{(x=unorm(x*norm(args)))...});}
template<typename...Args>
constexpr _Tp sum(Args...args)const{
_Tp ret{0};
return plus(ret,args...),ret;
}
template<typename...Args>
constexpr _Tp prod(Args...args)const{
_Tp ret{1};
return mult(ret,args...),ret;
}
template<typename T>
constexpr _Tp qpow(_Tp x,T pw)const{
_Tp ret{1};
x=norm(x);
for(;pw;pw>>=1,x=unorm(x*x)) if(pw&1) ret=unorm(ret*x);
return ret;
}
constexpr _Tp inv(_Tp x)const{return qpow(x,phi-1);}
template<size_t N>
constexpr auto getFac(){
std::array<_Tp,N> Fac{};
Fac[0]=1;
for(size_t i=1;i<N;++i) Fac[i]=unorm(Fac[i-1]*i);
return Fac;
}
template<size_t N>
constexpr auto getInv(_Tp Fac){
std::array<_Tp,N> Inv{};
Inv[N-1]=inv(Fac),Inv[0]=1;
for(size_t i=N-2;i;--i) Inv[i]=unorm(Inv[i+1]*(i+1));
return Inv;
}
};
}
namespace DS{
namespace Sgt{
enum SegmentTree_Type{Single=1,Interval=2};
template<typename Info,SegmentTree_Type _Modify,SegmentTree_Type _Query,typename Vec=std::vector<Info>>
class SegmentTree{};
template<typename Info,typename Vec>
class SegmentTree<Info,Interval,Interval,Vec>{
private:
int st,ed;
Vec tr;
void build(int p,int l,int r){
tr[p]={};
if(l==r) return tr[p].init(l);
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
tr[p].pull(tr[p<<1],tr[p<<1|1]);
}
void modify(int p,int l,int r,int L,int R,const Info&V){
if(L<=l&&r<=R) return tr[p].get(V);
int mid=(l+r)>>1;
tr[p].push(tr[p<<1],tr[p<<1|1]);
if(L<=mid) modify(p<<1,l,mid,L,R,V);
if(R>mid) modify(p<<1|1,mid+1,r,L,R,V);
tr[p].pull(tr[p<<1],tr[p<<1|1]);
}
Info query(int p,int l,int r,int L,int R){
if(L<=l&&r<=R) return tr[p];
int mid=(l+r)>>1;
tr[p].push(tr[p<<1],tr[p<<1|1]);
if(L<=mid&&R>mid) return merge(query(p<<1,l,mid,L,R),query(p<<1|1,mid+1,r,L,R));
else return L<=mid?query(p<<1,l,mid,L,R):query(p<<1|1,mid+1,r,L,R);
}
public:
SegmentTree():st{},ed{},tr{}{}
SegmentTree(int _st,int _ed):st{_st},ed{_ed}{tr.resize((ed-st+1)<<2);}
void build(){build(1,st,ed);}
void resize(int _st,int _ed){st=_st,ed=_ed,tr.resize((ed-st+1)<<2);}
void modify(int L,int R,const Info&V){modify(1,st,ed,L,R,V);}
Info query(int L,int R){return query(1,st,ed,L,R);}
void modify(int X,const Info&V){modify(1,st,ed,X,X,V);}
Info query(int X){return query(1,st,ed,X,X);}
};
}
}
namespace NetFlow{
template<typename _Cap,template<typename...> typename _Vec=std::vector>
class Maxi_Flow{
struct edge{int ver,nxt;_Cap cap;};
_Vec<int> Head;
_Vec<edge> Edge;
public:
using edge_type=edge;
using edge_point=int;
edge_point edgeEnd()const{return -1;}
edge_point edgeRev(edge_point e)const{return e^1;}
Maxi_Flow():Head{},Edge{},Dep{}{}
Maxi_Flow(int n):Edge{}{Head.resize(n,-1),Dep.resize(n),Que.resize(n);}
Maxi_Flow(int n,int m){Head.resize(n,-1),Edge.reserve(m<<1),Dep.resize(n),Que.resize(n);}
void clear(){std::fill(Head.begin(),Head.end(),-1),Edge.clear();}
void resize(int n){Head.clear(),Head.resize(n,-1),Dep.resize(n),Que.resize(n);}
void resize(int n,int m){Head.clear(),Head.resize(n,-1),Edge.reserve(m<<1),Dep.resize(n),Que.resize(n);}
edge_point add(int u,int v,_Cap c){return Edge.push_back({v,Head[u],c}),Head[u]=Edge.size()-1;}
edge_point link(int u,int v,_Cap c){return add(v,u,0),add(u,v,c);}
const edge_point&getHead(int u)const{return Head[u];}
const edge_type&getEdge(edge_point e)const{return Edge[e];}
edge_type&cgEdge(edge_point e){return Edge[e];}
private:
_Vec<int> Dep,Cur,Que;
bool bfs(int s,int t){
std::fill(Dep.begin(),Dep.end(),-1);
Que.resize(Head.size());
static int head,tail;
Dep[Que[head=tail=0]=s]=0;
for(int u;head<=tail;) for(int e=Head[u=Que[head++]];~e;e=Edge[e].nxt)
if(Edge[e].cap&&!~Dep[Edge[e].ver]) Dep[Que[++tail]=Edge[e].ver]=Dep[u]+1;
return Dep[t]!=-1;
}
_Cap dfs(int u,int t,_Cap flow){
if(u==t) return flow;
_Cap rest=flow;
for(int&e=Cur[u];~e&&rest;e=Edge[e].nxt)
if(Edge[e].cap&&Dep[Edge[e].ver]==Dep[u]+1){
_Cap cap=dfs(Edge[e].ver,t,min(rest,Edge[e].cap));
if(cap!=0) Edge[e].cap-=cap,Edge[edgeRev(e)].cap+=cap,rest-=cap;
else Dep[Edge[e].ver]=-1;
}
return flow-rest;
}
public:
void output(){for(auto i=0u;i<Head.size();++i) for(int e=Head[i];~e;e=Edge[e].nxt) if(Edge[e].cap) printf("%d %d %d\n",i,Edge[e].ver,Edge[e].cap);}
_Cap flow(int s,int t,_Cap limit=Inf<_Cap>){
_Cap flow{};
while(limit&&bfs(s,t)) for(Cur=Head;_Cap cap=dfs(s,t,limit);) flow+=cap,limit-=cap;
return flow;
}
};
template<typename _Cap,typename _Cost,template<typename...> typename _Vec=std::vector,template<typename...> typename _Que=std::queue>
class Mini_Cost_Maxi_Flow{
struct edge{int ver,nxt;_Cap cap;_Cost cost;};
_Vec<int> Head;
_Vec<edge> Edge;
public:
using edge_type=edge;
using edge_point=int;
edge_point edgeEnd()const{return -1;}
edge_point edgeRev(edge_point e)const{return e^1;}
Mini_Cost_Maxi_Flow():Head{},Edge{}{}
Mini_Cost_Maxi_Flow(int n):Edge{}{Head.resize(n,-1),Dis.resize(n),Inq.resize(n);}
Mini_Cost_Maxi_Flow(int n,int m){Head.resize(n,-1),Edge.reserve(m<<1),Dis.resize(n),Inq.resize(n);}
void clear(){std::fill(Head.begin(),Head.end(),-1),Edge.clear();}
void resize(int n){Head.clear(),Head.resize(n,-1),Dis.resize(n),Inq.resize(n);}
void resize(int n,int m){Head.clear(),Head.resize(n,-1),Edge.reserve(m<<1),Dis.resize(n),Inq.resize(n);}
edge_point add(int u,int v,_Cap c,_Cost w){return Edge.push_back({v,Head[u],c,w}),Head[u]=Edge.size()-1;}
edge_point link(int u,int v,_Cap c,_Cost w){return add(v,u,0,-w),add(u,v,c,w);}
const edge_point&getHead(int u)const{return Head[u];}
const edge_type&getEdge(edge_point e)const{return Edge[e];}
private:
_Vec<int> Cur,Inq;
_Vec<_Cost> Dis;
bool spfa(int s,int t){
std::fill(Dis.begin(),Dis.end(),Inf<_Cost>);
std::fill(Inq.begin(),Inq.end(),0);
static _Que<int> q;
q.emplace(s),Dis[s]=0,Inq[s]=1;
for(int u;!q.empty();){
Inq[u=q.front()]=0,q.pop();
for(int e=Head[u];~e;e=Edge[e].nxt)
if(Edge[e].cap&&Dis[Edge[e].ver]>Dis[u]+Edge[e].cost)
if(Dis[Edge[e].ver]=Dis[u]+Edge[e].cost,!Inq[Edge[e].ver]) q.emplace(Edge[e].ver),Inq[Edge[e].ver]=1;
}
return Dis[t]!=Inf<_Cost>;
}
_Cap dfs(int u,int t,_Cap flow){
if(u==t) return flow;
_Cap rest=flow;
Inq[u]=1;
for(int&e=Cur[u];~e&&rest;e=Edge[e].nxt)
if(Edge[e].cap&&!Inq[Edge[e].ver]&&Dis[Edge[e].ver]==Dis[u]+Edge[e].cost){
_Cap cap=dfs(Edge[e].ver,t,min(rest,Edge[e].cap));
if(cap!=0) Edge[e].cap-=cap,Edge[edgeRev(e)].cap+=cap,rest-=cap;
else Dis[Edge[e].ver]=Inf<_Cost>;
}
Inq[0]=1;
return flow-rest;
}
public:
void output(){for(auto i=0u;i<Head.size();++i) for(int e=Head[i];~e;e=Edge[e].nxt) if(Edge[e].cap) printf("%d %d %d\n",i,Edge[e].ver,Edge[e].cap);}
std::pair<_Cap,_Cost> flow(int s,int t,_Cap limit=Inf<_Cap>){
_Cap flow{};
_Cost cost{};
while(limit&&spfa(s,t)) for(Cur=Head;_Cap cap=dfs(s,t,limit);) flow+=cap,limit-=cap,cost+=cap*Dis[t];
return {flow,cost};
}
};
}
namespace Mat{
template<typename T>
class Matrix{
protected:
int n,m;
int**v;
void Alloca(){
if(n>0&&m>0){
v=new int*[n]{};
for(int i=0;i<n;++i) v[i]=new int[m]{};
}
else v=nullptr,n=m=0;
}
void Freeze(){
if(n>0&&m>0){
for(int i=0;i<n;++i) delete[] v[i];
delete[] v;
}
v=nullptr,n=m=0;
}
void clone(int**p){for(int i=0;i<n;++i) for(int j=0;j<m;++j) v[i][j]=p[i][j];}
public:
int row()const{return n;}
int col()const{return m;}
Matrix():n{},m{},v{}{}
Matrix(int _n,int _m):n{_n},m{_m},v{}{Alloca();}
Matrix(int _n):n{_n},m{_n},v{}{Alloca(),init();}
Matrix(const Matrix&it):n{it.n},m{it.m}{Alloca(),clone(it.v);}
Matrix(Matrix&&it):Matrix{}{swap(n,it.n),swap(m,it.m),swap(v,it.v);}
Matrix&operator=(const Matrix&it){return resize(it.n,it.m),clone(it.v),*this;}
Matrix&operator=(Matrix&&it){return swap(n,it.n),swap(m,it.m),swap(v,it.v),*this;}
void resize(int _n,int _m,int _v={}){
Freeze(),n=_n,m=_m,Alloca();
for(int i=0;i<n;++i) for(int j=0;j<m;++j) v[i][j]=_v;
}
T*operator[](int x){return v[x];}
const T*operator[](int x)const{return v[x];}
void init(){for(int i=0;i<n;++i) (*this)[i][i]=1;}
~Matrix(){Freeze();}
template<typename U>
operator Matrix<U>()const{
Matrix<U> ret(n,m);
return ret.Alloca(),ret.clone(v),ret;
}
};
template<typename Flush,typename T>
IO::OutStream<Flush>&operator<<(IO::OutStream<Flush>&os,const Matrix<T>&it){
for(int i=0;i<it.row();++i,os<<'\n') for(int j=0;j<it.col();++j) os<<it[i][j]<<' ';
return os;
}
}
/**
* Bug still stay.
*/
namespace String{
// class string{
// static constexpr int MaxLen=1.5e5;
// unsigned len;
// char str[MaxLen];
// public:
// unsigned length()const{return len;}
// string(char ch):len{},str{}{str[len++]=ch;}
// string(const char*s=""):len{},str{}{
// for(;*s;++s) str[len++]=*s;
// str[len]='\0';
// }
// string(char*s):string{static_cast<const char*>(s)}{}
// string(string&&s):string{s.str}{}
// string&operator+=(const string&s){
// for(int i=0;i<s.len;++i) str[len++]=s[i];
// return str[len]='\0',*this;
// }
// char&operator[](unsigned x){return str[x];}
// const char&operator[](unsigned x)const{return str[x];}
// friend string operator+(string lhs,const string&rhs){return lhs+=rhs;}
// friend string operator+(const char*lhs,const string&rhs){return string(lhs)+=rhs;}
// friend string operator+(char*lhs,const string&rhs){return string(lhs)+=rhs;}
// operator const char*()const{return str;}
// const char*c_str()const{return str;}
// };
// template<typename Flush>
// IO::OutStream<Flush>&operator<<(IO::OutStream<Flush>&os,const string&s){
// for(unsigned i=0;i<s.length();++i) os<<s[i];
// return os;
// }
}
}
using namespace Default_Source;
/**
* 证明超帅。
* 一个是根据点的位置,写不等式,然后根据角度列方程:
* - k>=x*(90/90+1)+y*(180/90+1)+z*(360/90+1)
* - k*180=x*90+y*180+z*360
* 其中 x=4 为角上的点,y 为边上的,z 为正方形中的散点。
* 然后化一下 k=y+2*z+2,同时可以有 k>=8。
* 另外的又可以发现每个三角形能拆成四个,拆法即连中位线,于是只需构造 8,9,10
* 帅气。
*/
IO::InStream<> Input;
IO::OutStream<> Output;
struct Point{int x,y;};
Point operator+(Point lhs,Point rhs){return {lhs.x+rhs.x,lhs.y+rhs.y};}
Point operator*(Point p,int v){return {p.x*v,p.y*v};}
Point operator/(Point p,int v){return {p.x/v,p.y/v};}
template<typename Flush>
IO::OutStream<Flush>&operator<<(IO::OutStream<Flush>&os,const Point&it){return os<<it.x<<' '<<it.y;}
template<typename Flush>
IO::OutStream<Flush>&operator<<(IO::OutStream<Flush>&os,const std::tuple<Point,Point,Point>&it){return os<<std::get<0>(it)<<' '<<std::get<1>(it)<<' '<<std::get<2>(it);}
constexpr std::tuple<Point,Point,Point> Eight[]{
{{0,0},{9,4},{0,20}},
{{0,20},{9,4},{10,20}},
{{10,20},{9,4},{11,4}},
{{10,20},{11,4},{20,20}},
{{20,0},{20,20},{11,4}},
{{0,0},{10,0},{9,4}},
{{10,0},{11,4},{9,4}},
{{10,0},{20,0},{11,4}}
};
constexpr std::tuple<Point,Point,Point> Nine[]{
{{0,0},{20,0},{16,12}},
{{0,0},{16,12},{0,20}},
{{0,20},{12,14},{13,20}},
{{20,0},{20,13},{16,12}},
{{16,16},{16,12},{20,13}},
{{16,16},{20,13},{20,20}},
{{16,16},{20,20},{13,20}},
{{16,16},{13,20},{12,14}},
{{16,16},{12,14},{16,12}}
};
constexpr std::tuple<Point,Point,Point> Ten[]{
{{0,0},{10,8},{0,20}},
{{20,0},{10,8},{20,20}},
{{0,20},{10,8},{20,20}},
{{0,0},{8,0},{5,4}},
{{10,3},{5,4},{8,0}},
{{10,3},{10,8},{5,4}},
{{10,3},{8,0},{12,0}},
{{10,3},{12,0},{15,4}},
{{10,3},{15,4},{10,8}},
{{20,0},{15,4},{12,0}}
};
constexpr int Ex=5e7;
template<int LEN,const std::tuple<Point,Point,Point>(&p)[LEN]>
void solve(unsigned n){
Output.writeln("Yes");
std::queue<std::tuple<Point,Point,Point>> q;
for(auto [x,y,z]:p) q.emplace(x*Ex,y*Ex,z*Ex);
while(q.size()<n){
auto [x,y,z]=q.front();
q.pop();
auto a=(x+y)/2,b=(y+z)/2,c=(x+z)/2;
q.emplace(a,c,x),q.emplace(a,b,y),q.emplace(b,c,z),q.emplace(a,b,c);
}
while(!q.empty()) Output.writeln(q.front()),q.pop();
}
signed main(){
int n=Input.read<int>();
if(n<8) Output.write("No");
else switch((n-8)%3){
case 0: solve<8,Eight>(n);break;
case 1: solve<9,Nine>(n);break;
case 2: solve<10,Ten>(n);break;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3508kb
input:
2
output:
No
result:
ok no solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
24
output:
Yes 800000000 800000000 1000000000 650000000 1000000000 1000000000 800000000 800000000 1000000000 1000000000 650000000 1000000000 800000000 800000000 650000000 1000000000 600000000 700000000 800000000 800000000 600000000 700000000 800000000 600000000 500000000 0 400000000 300000000 0 0 500000000 0 9...
result:
ok 24 acute triangles
Test #3:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
1
output:
No
result:
ok no solution
Test #4:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3
output:
No
result:
ok no solution
Test #5:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
4
output:
No
result:
ok no solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
5
output:
No
result:
ok no solution
Test #7:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
6
output:
No
result:
ok no solution
Test #8:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
7
output:
No
result:
ok no solution
Test #9:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
8
output:
Yes 0 0 450000000 200000000 0 1000000000 0 1000000000 450000000 200000000 500000000 1000000000 500000000 1000000000 450000000 200000000 550000000 200000000 500000000 1000000000 550000000 200000000 1000000000 1000000000 1000000000 0 1000000000 1000000000 550000000 200000000 0 0 500000000 0 450000000 ...
result:
ok 8 acute triangles
Test #10:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
9
output:
Yes 0 0 1000000000 0 800000000 600000000 0 0 800000000 600000000 0 1000000000 0 1000000000 600000000 700000000 650000000 1000000000 1000000000 0 1000000000 650000000 800000000 600000000 800000000 800000000 800000000 600000000 1000000000 650000000 800000000 800000000 1000000000 650000000 1000000000 1...
result:
ok 9 acute triangles
Test #11:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
10
output:
Yes 0 0 500000000 400000000 0 1000000000 1000000000 0 500000000 400000000 1000000000 1000000000 0 1000000000 500000000 400000000 1000000000 1000000000 0 0 400000000 0 250000000 200000000 500000000 150000000 250000000 200000000 400000000 0 500000000 150000000 500000000 400000000 250000000 200000000 5...
result:
ok 10 acute triangles
Test #12:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
11
output:
Yes 0 1000000000 450000000 200000000 500000000 1000000000 500000000 1000000000 450000000 200000000 550000000 200000000 500000000 1000000000 550000000 200000000 1000000000 1000000000 1000000000 0 1000000000 1000000000 550000000 200000000 0 0 500000000 0 450000000 200000000 500000000 0 550000000 20000...
result:
ok 11 acute triangles
Test #13:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
12
output:
Yes 0 0 800000000 600000000 0 1000000000 0 1000000000 600000000 700000000 650000000 1000000000 1000000000 0 1000000000 650000000 800000000 600000000 800000000 800000000 800000000 600000000 1000000000 650000000 800000000 800000000 1000000000 650000000 1000000000 1000000000 800000000 800000000 1000000...
result:
ok 12 acute triangles
Test #14:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
13
output:
Yes 1000000000 0 500000000 400000000 1000000000 1000000000 0 1000000000 500000000 400000000 1000000000 1000000000 0 0 400000000 0 250000000 200000000 500000000 150000000 250000000 200000000 400000000 0 500000000 150000000 500000000 400000000 250000000 200000000 500000000 150000000 400000000 0 600000...
result:
ok 13 acute triangles
Test #15:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
14
output:
Yes 500000000 1000000000 450000000 200000000 550000000 200000000 500000000 1000000000 550000000 200000000 1000000000 1000000000 1000000000 0 1000000000 1000000000 550000000 200000000 0 0 500000000 0 450000000 200000000 500000000 0 550000000 200000000 450000000 200000000 500000000 0 1000000000 0 5500...
result:
ok 14 acute triangles
Test #16:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
15
output:
Yes 0 1000000000 600000000 700000000 650000000 1000000000 1000000000 0 1000000000 650000000 800000000 600000000 800000000 800000000 800000000 600000000 1000000000 650000000 800000000 800000000 1000000000 650000000 1000000000 1000000000 800000000 800000000 1000000000 1000000000 650000000 1000000000 8...
result:
ok 15 acute triangles
Test #17:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
16
output:
Yes 0 1000000000 500000000 400000000 1000000000 1000000000 0 0 400000000 0 250000000 200000000 500000000 150000000 250000000 200000000 400000000 0 500000000 150000000 500000000 400000000 250000000 200000000 500000000 150000000 400000000 0 600000000 0 500000000 150000000 600000000 0 750000000 2000000...
result:
ok 16 acute triangles
Test #18:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
17
output:
Yes 500000000 1000000000 550000000 200000000 1000000000 1000000000 1000000000 0 1000000000 1000000000 550000000 200000000 0 0 500000000 0 450000000 200000000 500000000 0 550000000 200000000 450000000 200000000 500000000 0 1000000000 0 550000000 200000000 225000000 100000000 0 500000000 0 0 225000000...
result:
ok 17 acute triangles
Test #19:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
18
output:
Yes 1000000000 0 1000000000 650000000 800000000 600000000 800000000 800000000 800000000 600000000 1000000000 650000000 800000000 800000000 1000000000 650000000 1000000000 1000000000 800000000 800000000 1000000000 1000000000 650000000 1000000000 800000000 800000000 650000000 1000000000 600000000 7000...
result:
ok 18 acute triangles
Test #20:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
19
output:
Yes 0 0 400000000 0 250000000 200000000 500000000 150000000 250000000 200000000 400000000 0 500000000 150000000 500000000 400000000 250000000 200000000 500000000 150000000 400000000 0 600000000 0 500000000 150000000 600000000 0 750000000 200000000 500000000 150000000 750000000 200000000 500000000 40...
result:
ok 19 acute triangles
Test #21:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
20
output:
Yes 1000000000 0 1000000000 1000000000 550000000 200000000 0 0 500000000 0 450000000 200000000 500000000 0 550000000 200000000 450000000 200000000 500000000 0 1000000000 0 550000000 200000000 225000000 100000000 0 500000000 0 0 225000000 100000000 225000000 600000000 450000000 200000000 225000000 60...
result:
ok 20 acute triangles
Test #22:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
21
output:
Yes 800000000 800000000 800000000 600000000 1000000000 650000000 800000000 800000000 1000000000 650000000 1000000000 1000000000 800000000 800000000 1000000000 1000000000 650000000 1000000000 800000000 800000000 650000000 1000000000 600000000 700000000 800000000 800000000 600000000 700000000 80000000...
result:
ok 21 acute triangles
Test #23:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
22
output:
Yes 500000000 150000000 250000000 200000000 400000000 0 500000000 150000000 500000000 400000000 250000000 200000000 500000000 150000000 400000000 0 600000000 0 500000000 150000000 600000000 0 750000000 200000000 500000000 150000000 750000000 200000000 500000000 400000000 1000000000 0 750000000 20000...
result:
ok 22 acute triangles
Test #24:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
23
output:
Yes 0 0 500000000 0 450000000 200000000 500000000 0 550000000 200000000 450000000 200000000 500000000 0 1000000000 0 550000000 200000000 225000000 100000000 0 500000000 0 0 225000000 100000000 225000000 600000000 450000000 200000000 225000000 600000000 0 500000000 0 1000000000 225000000 100000000 22...
result:
ok 23 acute triangles
Test #25:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
25
output:
Yes 500000000 150000000 500000000 400000000 250000000 200000000 500000000 150000000 400000000 0 600000000 0 500000000 150000000 600000000 0 750000000 200000000 500000000 150000000 750000000 200000000 500000000 400000000 1000000000 0 750000000 200000000 600000000 0 250000000 200000000 0 500000000 0 0...
result:
ok 25 acute triangles
Test #26:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
26
output:
Yes 500000000 0 550000000 200000000 450000000 200000000 500000000 0 1000000000 0 550000000 200000000 225000000 100000000 0 500000000 0 0 225000000 100000000 225000000 600000000 450000000 200000000 225000000 600000000 0 500000000 0 1000000000 225000000 100000000 225000000 600000000 0 500000000 225000...
result:
ok 26 acute triangles
Test #27:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
27
output:
Yes 800000000 800000000 1000000000 1000000000 650000000 1000000000 800000000 800000000 650000000 1000000000 600000000 700000000 800000000 800000000 600000000 700000000 800000000 600000000 500000000 0 400000000 300000000 0 0 500000000 0 900000000 300000000 1000000000 0 900000000 300000000 400000000 3...
result:
ok 27 acute triangles
Test #28:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
28
output:
Yes 500000000 150000000 400000000 0 600000000 0 500000000 150000000 600000000 0 750000000 200000000 500000000 150000000 750000000 200000000 500000000 400000000 1000000000 0 750000000 200000000 600000000 0 250000000 200000000 0 500000000 0 0 250000000 200000000 250000000 700000000 500000000 400000000...
result:
ok 28 acute triangles
Test #29:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
29
output:
Yes 500000000 0 1000000000 0 550000000 200000000 225000000 100000000 0 500000000 0 0 225000000 100000000 225000000 600000000 450000000 200000000 225000000 600000000 0 500000000 0 1000000000 225000000 100000000 225000000 600000000 0 500000000 225000000 600000000 250000000 1000000000 0 1000000000 2250...
result:
ok 29 acute triangles
Test #30:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
30
output:
Yes 800000000 800000000 650000000 1000000000 600000000 700000000 800000000 800000000 600000000 700000000 800000000 600000000 500000000 0 400000000 300000000 0 0 500000000 0 900000000 300000000 1000000000 0 900000000 300000000 400000000 300000000 800000000 600000000 500000000 0 900000000 300000000 40...
result:
ok 30 acute triangles
Test #31:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
31
output:
Yes 500000000 150000000 600000000 0 750000000 200000000 500000000 150000000 750000000 200000000 500000000 400000000 1000000000 0 750000000 200000000 600000000 0 250000000 200000000 0 500000000 0 0 250000000 200000000 250000000 700000000 500000000 400000000 250000000 700000000 0 500000000 0 100000000...
result:
ok 31 acute triangles
Test #32:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
32
output:
Yes 225000000 100000000 0 500000000 0 0 225000000 100000000 225000000 600000000 450000000 200000000 225000000 600000000 0 500000000 0 1000000000 225000000 100000000 225000000 600000000 0 500000000 225000000 600000000 250000000 1000000000 0 1000000000 225000000 600000000 475000000 600000000 450000000...
result:
ok 32 acute triangles
Test #33:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
33
output:
Yes 800000000 800000000 600000000 700000000 800000000 600000000 500000000 0 400000000 300000000 0 0 500000000 0 900000000 300000000 1000000000 0 900000000 300000000 400000000 300000000 800000000 600000000 500000000 0 900000000 300000000 400000000 300000000 400000000 300000000 0 500000000 0 0 4000000...
result:
ok 33 acute triangles
Test #34:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
34
output:
Yes 500000000 150000000 750000000 200000000 500000000 400000000 1000000000 0 750000000 200000000 600000000 0 250000000 200000000 0 500000000 0 0 250000000 200000000 250000000 700000000 500000000 400000000 250000000 700000000 0 500000000 0 1000000000 250000000 200000000 250000000 700000000 0 50000000...
result:
ok 34 acute triangles
Test #35:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
35
output:
Yes 225000000 100000000 225000000 600000000 450000000 200000000 225000000 600000000 0 500000000 0 1000000000 225000000 100000000 225000000 600000000 0 500000000 225000000 600000000 250000000 1000000000 0 1000000000 225000000 600000000 475000000 600000000 450000000 200000000 475000000 600000000 25000...
result:
ok 35 acute triangles
Test #36:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
36
output:
Yes 500000000 0 400000000 300000000 0 0 500000000 0 900000000 300000000 1000000000 0 900000000 300000000 400000000 300000000 800000000 600000000 500000000 0 900000000 300000000 400000000 300000000 400000000 300000000 0 500000000 0 0 400000000 300000000 400000000 800000000 800000000 600000000 4000000...
result:
ok 36 acute triangles
Test #37:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
37
output:
Yes 1000000000 0 750000000 200000000 600000000 0 250000000 200000000 0 500000000 0 0 250000000 200000000 250000000 700000000 500000000 400000000 250000000 700000000 0 500000000 0 1000000000 250000000 200000000 250000000 700000000 0 500000000 750000000 200000000 1000000000 500000000 1000000000 0 7500...
result:
ok 37 acute triangles
Test #38:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
38
output:
Yes 225000000 600000000 0 500000000 0 1000000000 225000000 100000000 225000000 600000000 0 500000000 225000000 600000000 250000000 1000000000 0 1000000000 225000000 600000000 475000000 600000000 450000000 200000000 475000000 600000000 250000000 1000000000 500000000 1000000000 225000000 600000000 475...
result:
ok 38 acute triangles
Test #39:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
39
output:
Yes 500000000 0 900000000 300000000 1000000000 0 900000000 300000000 400000000 300000000 800000000 600000000 500000000 0 900000000 300000000 400000000 300000000 400000000 300000000 0 500000000 0 0 400000000 300000000 400000000 800000000 800000000 600000000 400000000 800000000 0 500000000 0 100000000...
result:
ok 39 acute triangles
Test #40:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
40
output:
Yes 250000000 200000000 0 500000000 0 0 250000000 200000000 250000000 700000000 500000000 400000000 250000000 700000000 0 500000000 0 1000000000 250000000 200000000 250000000 700000000 0 500000000 750000000 200000000 1000000000 500000000 1000000000 0 750000000 200000000 750000000 700000000 500000000...
result:
ok 40 acute triangles
Test #41:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
41
output:
Yes 225000000 100000000 225000000 600000000 0 500000000 225000000 600000000 250000000 1000000000 0 1000000000 225000000 600000000 475000000 600000000 450000000 200000000 475000000 600000000 250000000 1000000000 500000000 1000000000 225000000 600000000 475000000 600000000 250000000 1000000000 4750000...
result:
ok 41 acute triangles
Test #42:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
42
output:
Yes 900000000 300000000 400000000 300000000 800000000 600000000 500000000 0 900000000 300000000 400000000 300000000 400000000 300000000 0 500000000 0 0 400000000 300000000 400000000 800000000 800000000 600000000 400000000 800000000 0 500000000 0 1000000000 400000000 300000000 400000000 800000000 0 5...
result:
ok 42 acute triangles
Test #43:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
43
output:
Yes 250000000 200000000 250000000 700000000 500000000 400000000 250000000 700000000 0 500000000 0 1000000000 250000000 200000000 250000000 700000000 0 500000000 750000000 200000000 1000000000 500000000 1000000000 0 750000000 200000000 750000000 700000000 500000000 400000000 750000000 700000000 10000...
result:
ok 43 acute triangles
Test #44:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
44
output:
Yes 225000000 600000000 250000000 1000000000 0 1000000000 225000000 600000000 475000000 600000000 450000000 200000000 475000000 600000000 250000000 1000000000 500000000 1000000000 225000000 600000000 475000000 600000000 250000000 1000000000 475000000 600000000 525000000 600000000 500000000 100000000...
result:
ok 44 acute triangles
Test #45:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
45
output:
Yes 500000000 0 900000000 300000000 400000000 300000000 400000000 300000000 0 500000000 0 0 400000000 300000000 400000000 800000000 800000000 600000000 400000000 800000000 0 500000000 0 1000000000 400000000 300000000 400000000 800000000 0 500000000 300000000 850000000 325000000 1000000000 0 10000000...
result:
ok 45 acute triangles
Test #46:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
46
output:
Yes 250000000 700000000 0 500000000 0 1000000000 250000000 200000000 250000000 700000000 0 500000000 750000000 200000000 1000000000 500000000 1000000000 0 750000000 200000000 750000000 700000000 500000000 400000000 750000000 700000000 1000000000 500000000 1000000000 1000000000 750000000 200000000 75...
result:
ok 46 acute triangles
Test #47:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
47
output:
Yes 225000000 600000000 475000000 600000000 450000000 200000000 475000000 600000000 250000000 1000000000 500000000 1000000000 225000000 600000000 475000000 600000000 250000000 1000000000 475000000 600000000 525000000 600000000 500000000 1000000000 475000000 600000000 500000000 200000000 450000000 20...
result:
ok 47 acute triangles
Test #48:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
48
output:
Yes 400000000 300000000 0 500000000 0 0 400000000 300000000 400000000 800000000 800000000 600000000 400000000 800000000 0 500000000 0 1000000000 400000000 300000000 400000000 800000000 0 500000000 300000000 850000000 325000000 1000000000 0 1000000000 300000000 850000000 625000000 850000000 600000000...
result:
ok 48 acute triangles
Test #49:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
49
output:
Yes 250000000 200000000 250000000 700000000 0 500000000 750000000 200000000 1000000000 500000000 1000000000 0 750000000 200000000 750000000 700000000 500000000 400000000 750000000 700000000 1000000000 500000000 1000000000 1000000000 750000000 200000000 750000000 700000000 1000000000 500000000 250000...
result:
ok 49 acute triangles
Test #50:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
50
output:
Yes 475000000 600000000 250000000 1000000000 500000000 1000000000 225000000 600000000 475000000 600000000 250000000 1000000000 475000000 600000000 525000000 600000000 500000000 1000000000 475000000 600000000 500000000 200000000 450000000 200000000 500000000 200000000 525000000 600000000 550000000 20...
result:
ok 50 acute triangles