結果

問題 No.5009 Draw A Convex Polygon
ユーザー kotatsugamekotatsugame
提出日時 2022-12-03 05:51:56
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,030 ms / 2,600 ms
コード長 961 bytes
コンパイル時間 685 ms
実行使用メモリ 27,764 KB
スコア 1,000,000
平均クエリ数 1000001.00
最終ジャッジ日時 2022-12-03 05:52:00
合計ジャッジ時間 3,684 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,030 ms
27,764 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int gcd(int a,int b)
{
	while(b)
	{
		int t=a%b;
		a=b;
		b=t;
	}
	return a;
}
int main()
{
	vector<pair<int,int> >A;
	for(int T=2;A.size()<250000;T++)for(int x=1;A.size()<250000&&x<T;x++)
	{
		int y=T-x;
		if(gcd(x,y)==1)A.push_back(make_pair(x,y));
	}
	sort(A.begin(),A.end(),[](pair<int,int>l,pair<int,int>r){
		return (long)l.first*r.second-(long)l.second*r.first>0;
	});
	int sy=0;
	for(pair<int,int>p:A)sy+=p.second;
	vector<pair<int,int> >ans;
	ans.push_back(make_pair(0,-sy));
	for(pair<int,int>p:A)ans.push_back(make_pair(ans.back().first+p.first,ans.back().second+p.second));
	{
		int n=ans.size();
		for(int i=n-2;i>=0;i--)ans.push_back(make_pair(ans[i].first,-ans[i].second));
	}
	{
		int n=ans.size();
		for(int i=n-2;i>0;i--)ans.push_back(make_pair(-ans[i].first,ans[i].second));
	}
	cout<<ans.size()<<"\n";
	for(pair<int,int>p:ans)cout<<p.first<<" "<<p.second<<"\n";
}
0