結果

問題 No.199 星を描こう
ユーザー srup٩(๑`н´๑)۶srup٩(๑`н´๑)۶
提出日時 2016-11-15 18:19:27
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,427 bytes
コンパイル時間 1,579 ms
コンパイル使用メモリ 168,044 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-26 01:51:39
合計ジャッジ時間 2,440 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;

inline double add(double a, double b){
    return abs(a+b)<(1e-10)*(abs(a)+abs(b)) ? 0.0 : a+b;
}
 
struct vec{
    double x,y;
    vec operator-(vec b){
        return (vec){add(x,-b.x),add(y,-b.y)};
    }
    vec operator+(vec b){
        return (vec){add(x,b.x),add(y,b.y)};
    }
    vec operator*(double d){
        return (vec){x*d,y*d};
    }
    double dot(vec v){
        return add(x*v.x,y*v.y);
    }
    double cross(vec v){
        return add(x*v.y,-y*v.x);
    }
    double norm(){
        return sqrt(x*x+y*y);
    }
};
 
int ccw(vec& a, vec& b, vec& c){
    vec ab = b-a, ac = c-a;
    double o = ab.cross(ac);
    if(o>0) return 1; //CCW
    if(o<0) return -1; //CW
    if(ab.dot(ac)<0){
        return 2; //C-A-B
    }else{
        if(ab.dot(ab)<ac.dot(ac)){
            return -2; //A-B-C
        }else{
            return 0; //A-C-B
        }
    }
}
 
vector<vec> convex_hull(vector<vec>& V){
    vector<vec> C;
    vector<vec>::iterator ite;
    sort(V.begin(),V.end(),[](const vec& a, const vec& b){return a.y==b.y ? a.x < b.x : a.y< b.y;});
    C.push_back(V[0]),C.push_back(V[1]);
    for(auto i=V.begin()+2; i!=V.end(); ++i){
        C.push_back(*i);        
        while(ite=C.end()-1, C.size()>2&&ccw(*(ite-2),*(ite-1),*ite)== -1){
            C.erase(ite-1);
        }
    }
    sort(V.begin(),V.end(),[](const vec& a, const vec& b){return a.y==b.y ? a.x > b.x : a.y>b.y;});
    for(auto i=V.begin()+1; i!=V.end(); ++i){
        C.push_back(*i);
        while(ite=C.end()-1, C.size()>2&&ccw(*(ite-2),*(ite-1),*ite)== -1){
            C.erase(ite-1);
        }
    }
    C.pop_back();
    return C;
}

int main(void){
	vector<vec> v;
	rep(i, 5){
		vec tmp;
		cin >> tmp.x >> tmp.y;
		v.push_back(tmp);
	}
	auto ret = convex_hull(v);
	// printf("%d\n", ret.size());
	if(ret.size() == 5){
		printf("YES\n");
	}else{
		printf("NO\n");
	}
	return 0;
}
0