QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#310936#5419. TrianglesqLAC ✓0ms3796kbC++2018.1kb2024-01-21 19:52:092024-01-21 19:52:09

Judging History

你现在查看的是最新测评结果

  • [2024-01-21 19:52:09]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3796kb
  • [2024-01-21 19:52:09]
  • 提交

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