結果
問題 | No.199 星を描こう |
ユーザー |
![]() |
提出日時 | 2023-04-04 04:26:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 1,541 bytes |
コンパイル時間 | 4,317 ms |
コンパイル使用メモリ | 258,204 KB |
最終ジャッジ日時 | 2025-02-11 22:47:29 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=long long; using ld=long double; ld pie=3.141592653589793; ll inf=144499999994; ll mod=1000000007; std::vector<std::pair<long long,long long>> convex_hull(std::vector<std::pair<long long,long long>> P){ /* Copyright (c) 2021 0214sh7 https://github.com/0214sh7/library/ */ if(P.size()<=2){ return P; } std::vector<std::pair<long long,long long>> H,L,R; sort(P.begin(),P.end()); //下半分 for(int i=0;i<P.size();i++){ int j=L.size(); while(j>=2 && (L[j-1].first-L[j-2].first)*(P[i].second-L[j-2].second)<=(L[j-1].second-L[j-2].second)*(P[i].first-L[j-2].first)){ L.pop_back(); j--; } L.push_back(P[i]); } //上半分 for(int i=P.size()-1;i>=0;i--){ int j=H.size(); while(j>=2 && (H[j-1].first-H[j-2].first)*(P[i].second-H[j-2].second)<=(H[j-1].second-H[j-2].second)*(P[i].first-H[j-2].first)){ H.pop_back(); j--; } H.push_back(P[i]); } R=L; for(int i=1;i<H.size()-1;i++){ R.push_back(H[i]); } return R; } int main(){ vector<pair<ll,ll>>p(5); for (ll i = 0; i < 5; i++) { ll x,y; cin >> x>> y; p[i]={x,y}; } sort(p.begin(),p.end()); auto a=convex_hull(p); if (a.size()==5) { cout << "YES"<< endl; }else{ cout << "NO" << endl; } }