結果

問題 No.199 星を描こう
コンテスト
ユーザー hiro71687k
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
    }
    
}
0