#23219 (C++11) No.199 星を描こう

提出ソース

結果

問題	No.199 星を描こう
ユーザー	Kmcode1
提出日時	2015-04-29 00:13:29
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	5,755 bytes
コンパイル時間	1,056 ms
コンパイル使用メモリ	117,224 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-06-09 13:45:59
合計ジャッジ時間	1,831 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	1 ms 6,940 KB
testcase_08	AC	1 ms 6,940 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	1 ms 6,944 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	1 ms 6,940 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	1 ms 6,944 KB
testcase_15	AC	1 ms 6,944 KB
testcase_16	AC	1 ms 6,940 KB
testcase_17	AC	1 ms 6,940 KB
testcase_18	AC	1 ms 6,944 KB
testcase_19	AC	1 ms 6,944 KB
testcase_20	AC	1 ms 6,940 KB
testcase_21	AC	1 ms 6,940 KB
testcase_22	AC	1 ms 6,948 KB
testcase_23	AC	1 ms 6,944 KB
testcase_24	AC	1 ms 6,944 KB
testcase_25	AC	1 ms 6,944 KB
testcase_26	AC	1 ms 6,940 KB
testcase_27	AC	1 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<valarray>
//#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
namespace math{
	long long int __gcd(long long int a, long long int b){
		if (a > b){
			swap(a, b);
		}
		while (a){
			swap(a, b);
			a %= b;
		}
		return b;
	}
	long long int lcm(long long int a, long long int b){
		long long int g = __gcd(a, b);
		a /= g;
		return a*b;
	}
	long long int ppow(long long int i, long long int j){
		long long int res = 1LL;
		while (j){
			if (j & 1LL){
				res *= i;
				res %= MOD;
			}
			i *= i;
			i %= MOD;
			j >>= 1LL;
		}
		return res;
	}
	namespace factorial{
		vector<long long int> lo;
		vector<double> l2;
		void set_long(long long int b){
			if (lo.size()){
			}
			else{
				lo.push_back(1);
			}
			for (long long int i = lo.size(); i <= b; i++){
				lo.push_back(lo.back());
				lo.back() *= i;
				if (lo.back() >= MOD){
					lo.back() %= MOD;
				}
			}
		}
		void set_log(long long int b){
			if (l2.size()){
			}
			else{
				l2.push_back(log(0.0));
			}
			for (long long int i = l2.size(); i <= b; i++){
				l2.push_back(l2.back());
				l2.back() += log((double)(i));
			}
		}
		long long int get_long(int b){
			if (lo.size() <= b){
				set_long(b);
			}
			return lo[b];
		}
		double get_log(int b){
			if (l2.size() <= b){
				set_log(b);
			}
			return l2[b];
		}
	}
	namespace combination{
		long long int simpleC(long long int a, long long int b){
			if (a < b){
				return 0;
			}
			if (a - b < b){
				b = a - b;
			}
			long long int u = 1LL;
			for (long long int j = a; j >= a - b + 1LL; j--){
				u *= j;
				if (u >= MOD){
					u %= MOD;
				}
			}
			long long int s = 1LL;
			for (long long int i = 1LL; i <= b; i++){
				s *= i;
				if (s >= MOD){
					s %= MOD;
				}
			}
			return (u*ppow(s, MOD - 2)) % MOD;
		}
		long long int C(long long int a, long long int b){
			if (a < b){
				return 0;
			}
			long long int u = math::factorial::get_long(a);
			long long int s = math::factorial::get_long(b)*math::factorial::get_long(a - b);
			u %= MOD;
			s %= MOD;
			return (u*ppow(s, MOD - 2)) % MOD;
		}
		double logC(int a, int b){
			double u = math::factorial::get_log(a);
			double s = math::factorial::get_log(b) + math::factorial::get_log(a - b);
			return u - s;
		}
		long long int H(long long int a, long long int b){
			return math::combination::C(a + b - 1LL, b);
		}
		long long int simpleH(long long int a, long long int b){
			return math::combination::simpleC(a + b - 1LL, b);
		}
	}
	namespace prime{
		vector<long long int> prime;
		vector<long long int> use;  //smallest divisor
		void init(int b){
			use.assign(b + 1, 0);
			prime.clear();
			prime.push_back(2);
			use[2] = 2;
			for (int i = 3; i < use.size(); i += 2){
				if (use[i] == 0LL){
					prime.push_back(i);
					use[i] = i;
					for (int j = i * 2; j < use.size(); j += i){
						use[j] = i;
					}
				}
			}
		}
		vector<int> factorizetion(long long int num){
			vector<int> r;
			r.clear();
			for (int i = 0; i<prime.size() && prime[i] * prime[i] <= num; i++){
				while (num%prime[i] == 0LL){
					r.push_back(prime[i]);
					num /= prime[i];
				}
			}
			if (num > 1LL){
				r.push_back(num);
			}
			return r;
		}
		int size_of_factorization(long long int num){
			int cnt = 0;
			for (int i = 0; i<prime.size() && prime[i] * prime[i] <= num; i++){
				while (num%prime[i] == 0LL){
					cnt++;
					num /= prime[i];
				}
			}
			if (num > 1LL){
				cnt++;
			}
			return cnt;
		}
		long long int number_of_div(long long int num){
			long long int way = 1LL;
			long long int cnt = 0;
			for (int i = 0; i < prime.size() && prime[i] * prime[i] <= num; i++){
				cnt = 0;
				while (num%prime[i] == 0){
					cnt++;
					num /= prime[i];
				}
				way *= (cnt + 1LL);
			}
			if (num > 1LL){
				way *= 2LL;
			}
			return way;
		}
	}
}

using namespace math;

struct st{
	int x;
	int y;
	int operator * (const st&a)const{
		return x*a.y - y*a.x;
	}
	bool operator < (const st&e)const{
		if (x != e.x){
			return e.x>x;
		}
		else{
			return e.y>y;
		}
	}
	st operator - (const st&b)const{
		st kari;
		kari.x = x - b.x;
		kari.y = y - b.y;
		return kari;
	}
};
vector<st> v;  //頂点の集合
vector<st> u;
vector<st> d;
vector<st> ans;
int nn = 0;  //頂点の数
void sol(){
	sort(v.begin(), v.end());
	/*下側*/
	{
		d = v;
		int ok = 1;
		while (ok){
			ok = 0;
			int i = 0;  //開始位置
			while (i<d.size() - 2){
				int j = i + 1;  //真ん中の点
				while (j<d.size() - 1){
					/*Cが右側にあるとき*/
					if ((d[j] - d[i])*(d[j + 1] - d[j]) <= 0){
						d.erase(j + d.begin(), j + 1 + d.begin());
						ok = 1;
					}
					else{
						break;
					}
				}
				i = j;
			}
		}
	}
	/*上側*/
	{
		u = v;
		int ok = 1;
		while (ok == 1){
			ok = 0;
			int i = 0;  //開始地点
			while (i<u.size() - 2){
				int j = i + 1;
				while (j<u.size() - 1){
					/*Cが左側にあるとき*/
					if ((u[j] - u[i])*(u[j + 1] - u[j]) >= 0){
						ok = 1;
						u.erase(j + u.begin(), j + 1 + u.begin());
					}
					else{
						break;
					}
				}
				i = j;
			}
		}
	}
	ans = d;
	for (int i = u.size() - 2; i >= 0; i--){
		ans.push_back(u[i]);
	}
}
int main(){
	nn = 5;
	for (int i = 0; i<nn; i++){
		st kari;
		cin >> kari.x >> kari.y;
		v.push_back(kari);
	}
	sol();
	if (ans.size() == 6){
		puts("YES");
	}
	else{
		puts("NO");
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード