結果
問題 | No.199 星を描こう |
ユーザー |
![]() |
提出日時 | 2016-08-31 01:48:01 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,498 bytes |
コンパイル時間 | 1,008 ms |
コンパイル使用メモリ | 90,388 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-30 03:53:30 |
合計ジャッジ時間 | 1,828 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <queue> #include "math.h" #include <complex> #include <iomanip> #include <map> #define ifor(i,a,b) for (int i=(a);i<(b);i++) #define rfor(i,a,b) for (int i=(b)-1;i>=(a);i--) #define rep(i,n) for (int i=0;i<(n);i++) #define rrep(i,n) for (int i=(n)-1;i>=0;i--) using namespace std; typedef long double ld; typedef complex<double> P; typedef long long lli; bool cmp_x(const P&p,const P&q){ if(p.real()!=q.real())return p.real()<q.real(); return p.imag()<q.imag(); } double dot(P a,P b){ //内積 return (conj(a)*b).real(); } double cross(P a,P b){ //det return (conj(a)*b).imag(); } P projection(P p,P b){ //bと原点を結ぶ直線に点pを投影 return b*dot(p,b)/norm(b); } int vex[4]={1,0,-1,0}; int vey[4]={0,1,0,-1}; typedef vector<double> Vec; typedef vector<int> vec; typedef vector<Vec> MAT; typedef vector<vec> mat; lli MOD=1000000007; vector<P>convex_hull(P* ps,int n){ sort(ps,ps+n,cmp_x); int k =0; vector<P>qs(n*2); rep(i,n){ while(k>1&&cross((qs[k-1]-qs[k-2]),(ps[i]-qs[k-1]))<=0)k--; qs[k++] = ps[i]; } for(int i = n-2,t=k;i>=0;i--){ while(k>t&&cross((qs[k-1]-qs[k-2]),(ps[i]-qs[k-1]))<=0)k--; qs[k++]=ps[i]; } qs.resize(k-1); return qs; } int main(){ P x[5]; double a,b; rep(i,5){ cin>>a>>b; x[i]=P(a,b); } vector<P> con= convex_hull(x,5); if(con.size()==5)cout<<"YES"<<endl; else cout<<"NO"<<endl; }