Submission #483225

#	Time	Username	Problem	Language	Result	Execution time	Memory
483225		Monarchuwu	Triangles (CEOI18_tri)	C++17	55 / 100	2275 ms	964 KiB

tri

/**
 *  - 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
**/

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 25