Submission #483225

#TimeUsernameProblemLanguageResultExecution timeMemory
483225MonarchuwuTriangles (CEOI18_tri)C++17
55 / 100
2275 ms964 KiB
/**
 *  - a làm gốc, b random, nếu tồn tại c thỏa cw(a, c, b) thì upd b = c
 *    => ta có 1 cạnh (a, b), sau đó tiếp tục lấy b làm gốc để tìm cạnh hull kế tiếp
 *  - lặp n lần, lúc này đỉnh gốc sẽ thuộc hull
 *  - lặp thêm n lần để add các đỉnh vào hull
**/
#include<iostream>
#include<algorithm>
#include<set>
#include "trilib.h"
using namespace std;
typedef long long ll;
int n;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    n = get_n();

    int a(1), b;
    for (int time = 0; time < n; ++time) {
        b = (a == 1 ? 2 : 1);
        for (int c = 1; c <= n; ++c)
            if (c != a && c != b && is_clockwise(a, c, b)) b = c;
        a = b;
    }

    set<int> s;
    for (int time = 0; time < n; ++time) {
        s.insert(a);
        b = (a == 1 ? 2 : 1);
        for (int c = 1; c <= n; ++c)
            if (c != a && c != b && is_clockwise(a, c, b)) b = c;
        a = b;
    }

    cout << s.size() << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...