結果

問題 No.199 星を描こう
ユーザー KKT89
提出日時 2019-09-03 13:59:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,798 bytes
コンパイル時間 1,048 ms
コンパイル使用メモリ 86,520 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-24 00:05:06
合計ジャッジ時間 2,170 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <complex>
using namespace std;
typedef long long int ll;

typedef complex<long double> Point;
typedef vector<Point> Polygon; // 多角形
const long double eps=1e-9;

namespace std{
    bool operator<(const Point &p,const Point &q){
    if(p.real()<q.real()-eps) return true;
    if(p.real()>q.real()+eps) return false;
    return p.imag()<q.imag();
    }
}

long double dot(Point a,Point b){ // 内積
    return real(conj(a)*b);
}
long double cross(Point a,Point b){ // 外積
    return imag(conj(a)*b);
}

//CCW
int ccw(Point a,Point b,Point c){
    b-=a; c-=a;
    if(cross(b,c)>eps){
        return 1; // a,b,cが反時計回りの順に並ぶ
    }
    if(cross(b,c)<-eps){
        return -1; // a,b,cが時計回りの順に並ぶ
    }
    if(dot(b,c)<0){
        return 2; // c,a,bがこの順に一直線に並ぶ
    }
    if(norm(b)<norm(c)){
        return -2; // a,b,cの順に一直線に並ぶ
    }
    return 0; // a,c,bの順に一直線に並ぶ
}

// 凸包：凸多角形のある一辺上にある点を含まない
Polygon convex_hull(vector<Point> ps){
    int n=(int)ps.size();
    int k=0; // 凸包の頂点数
    sort(ps.begin(),ps.end());
    Polygon qs(2*n); // 構築中の凸包
    for(int i=0;i<n;qs[k++]=ps[i++]){
        while(k>=2&&ccw(qs[k-2],qs[k-1],ps[i])<=0) --k;
    }
    for(int i=n-2,t=k+1;i>=0;qs[k++]=ps[i--]){
        while(k>=t&&ccw(qs[k-2],qs[k-1],ps[i])<=0) --k;
    }
    qs.resize(k-1);
    return qs;
}

int main(){
    Polygon ps(5);
    for(int i=0;i<5;i++){
        int x,y; cin >> x >> y;
        ps[i]=Point(x,y);
    }
    ps=convex_hull(ps);
    if(ps.size()==5){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}
0