結果

問題 No.199 星を描こう
コンテスト
ユーザー yaoshimax
提出日時 2015-04-29 00:07:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,704 bytes
コンパイル時間 1,200 ms
コンパイル使用メモリ 96,260 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-30 03:20:18
合計ジャッジ時間 2,192 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

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