結果
問題 | No.199 星を描こう |
ユーザー |
|
提出日時 | 2022-09-10 20:17:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 1,434 bytes |
コンパイル時間 | 4,321 ms |
コンパイル使用メモリ | 258,480 KB |
最終ジャッジ日時 | 2025-02-07 04:10:34 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using ll = long long; int n; vector<pair<ll,ll>> vpll; 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; } void solve(){ if(convex_hull(vpll).size()==n){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); n = 5; vpll = vector<pair<ll,ll>>(n); for(auto &[l,r]:vpll)cin >> l >> r; solve(); }