結果

問題 No.3154 convex polygon judge
ユーザー Ponzu
提出日時 2025-05-20 21:51:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,988 bytes
コンパイル時間 3,513 ms
コンパイル使用メモリ 280,780 KB
実行使用メモリ 12,456 KB
最終ジャッジ日時 2025-05-20 21:51:47
合計ジャッジ時間 7,314 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 4 TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

// find convex hull of 2D points using Graham scan
//https://qiita.com/hiro949/items/5573e801e50d638aeb52
#include<bits/stdc++.h>
#define rep(i,n) for ( int i=0; i< (n); ++i )
using namespace std;
using P = pair<int,int>;

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<P> &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<P> &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<P> &node ){
    int max_step = node.size()*node.size()*node.size(); // all combination of triangle = nC3
    int step = 0;
    int i = 0;
    while( i<node.size()-2 and step < max_step ){
        int area = signed_area( node[i+1], node[i+2], node[i] );
        // area < 0 => 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<P> &node ){
    // iterator of the node with min x components
    vector<P>::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<P> 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;
}
0