// find convex hull of 2D points using Graham scan //https://qiita.com/hiro949/items/5573e801e50d638aeb52 #include #define rep(i,n) for ( int i=0; i< (n); ++i ) using namespace std; using P = pair; P diff_pair( P p1, P p2 ){ // caculate difference of p1 from p2 int a = p1.first - p2.first; int b = p1.second - p2.second; return make_pair(a,b); } int signed_area( P p1, P p2, P p3 ){ // to chech relativistic position of 3 poins P v1 = diff_pair( p2,p1 ); P v2 = diff_pair( p3,p1 ); return v1.first*v2.second - v1.second*v2.first; // calc area as z-component of v1 x v2 } // partation for quick sort int partition (vector

&node, int l, int r, P p_minx) { P pivot = node[r]; int i = (l - 1); for (int j = l; j <= r - 1; j++) { // compare func : signed_area ~ Declination from p with min x // signed_area < 0 => clockwise if ( signed_area( p_minx, node[j], pivot ) >= 0 ) { i++; iter_swap(node.begin()+i, node.begin()+j); } } iter_swap(node.begin()+i+1, node.begin()+r); return (i + 1); } // sort points counter-clockwise void qsort_c_clockwise( vector

&node, int l, int r, P p_minx) { if (l < r) { int pivot = partition(node, l, r, p_minx); qsort_c_clockwise(node, l, pivot - 1,p_minx); qsort_c_clockwise(node, pivot + 1, r,p_minx); } return; } void remove_concave( vector

&node ){ int max_step = node.size()*node.size()*node.size(); // all combination of triangle = nC3 int step = 0; int i = 0; while( i line graph of these points dents // => remove concave point // => check for new set again if( area <= 0 ) { node.erase( node.begin()+i+1 ); i=0; }else{ ++i; } ++step; } return; } void graham_scan( vector

&node ){ // iterator of the node with min x components vector

::iterator itr_minx = min_element(node.begin(), node.end(), [](const P &l, const P &r) { return r.first > l.first; }); // move min element to head iter_swap( node.begin(), itr_minx ); qsort_c_clockwise ( node, 0, node.size()-1, node[0] ); remove_concave( node ); return; } int main(){ // input int N; cin >> N; //cout << "# of points = "; cin >> N; /* if( N<3 ){ cout << "N >= 3" << endl; exit(1); } */ vector

node(N); int x,y; rep(i,N){ cin >> x >> y; node[i] = make_pair(x,y); } graham_scan( node ); // output /* cout << "nodes of the convex hull :" << endl; for( P p : node ){ cout << p.first << " " << p.second << endl; } */ if(node.size() == N) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; }