結果

問題 No.199 星を描こう
ユーザー yaoshimaxyaoshimax
提出日時 2015-04-29 00:07:15
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,704 bytes
コンパイル時間 1,093 ms
コンパイル使用メモリ 95,448 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-09 13:44:56
合計ジャッジ時間 1,607 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 1 ms
6,944 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 1 ms
6,944 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 1 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 1 ms
6,940 KB
testcase_19 AC 1 ms
6,944 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 AC 1 ms
6,940 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 1 ms
6,940 KB
testcase_25 AC 1 ms
6,940 KB
testcase_26 AC 1 ms
6,940 KB
testcase_27 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <queue>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;

long long product( pair<int,int> p1, pair<int,int> p2, pair<int,int> p3 ){
   pair<int,int> v1 = make_pair( p2.first-p1.first, p2.second-p1.second);
   pair<int,int> v2 = make_pair( p3.first-p1.first, p3.second-p1.second);
   return v2.first*(long long)v1.second-v2.second*(long long)v1.first;
}

vector< pair<int,int> > convex_hull( vector<pair<int,int> > &V){
   if( V.size() <=2 ) return V;
   int size = V.size();
   sort(V.begin(),V.end());
   vector<pair<int,int> > ret(size*2);
   int retlen=0; 
   for( int i = 0 ; i <size; i++ ){
      while( retlen >= 2 && product( ret[retlen-2],ret[retlen-1],V[i] ) <= 0 ) retlen--;
      ret[retlen++]=V[i];
   }
   int underlen=retlen;
   for( int i = size-2 ; i >= 0 ; i-- ){
      while( retlen > underlen && product( ret[retlen-2],ret[retlen-1],V[i] ) <= 0 ) retlen--;
      ret[retlen++]=V[i];
   }
   ret.resize(retlen);
   return ret;
}

int main(){
   vector<pair<int,int> >V;
   for( int i = 0 ; i < 5; i++ ){
      pair<int,int> p;
      cin >> p.first >> p.second;
      V.push_back(p);
   }
   vector<pair<int,int> > ch=convex_hull(V);
   /*
   for( int i = 0 ; i < (int)ch.size() ; i++){
      cout << ch[i].first <<","<<ch[i].second<<endl;
   }*/
   if( ch.size() ==6 ){
      cout <<"YES"<<endl;
   }
   else{
      cout <<"NO"<<endl;
   }
   return 0;
}
0