結果

問題 No.199 星を描こう
ユーザー KKT89KKT89
提出日時 2019-09-03 13:59:02
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,798 bytes
コンパイル時間 954 ms
コンパイル使用メモリ 86,552 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-06 09:45:08
合計ジャッジ時間 1,967 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 1 ms
6,944 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 1 ms
6,944 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 AC 1 ms
6,944 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 1 ms
6,948 KB
testcase_27 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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