Submission #321202

#	Time	Username	Problem	Language	Result	Execution time	Memory
321202		phathnv	Triangles (CEOI18_tri)	C++11	100 / 100	31 ms	2660 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"

#define mp make_pair
#define X first
#define Y second
#define taskname "Triangle"

using namespace std;

typedef long long ll;
typedef pair <int, int> point;

const int N = 40001;
int _n, ind[N], type[N];

int main(){
    _n = get_n();
    for(int i = 1; i <= _n; i++)
        ind[i] = i;
    type[1] = 0;
    type[2] = 1;
    for(int i = 3; i <= _n; i++)
        type[i] = !is_clockwise(1, 2, i);
    sort(ind + 2, ind + 1 + _n, [](const int &a, const int &b){
            bool tA = type[a];
            bool tB = type[b];
            if (tA != tB)
                return tB;
            if (a == 2)
                return true;
            if (b == 2)
                return false;
            return (!is_clockwise(1, a, b));
         });

    vector <int> st;
    st.push_back(1);
    for(int i = 2; i <= _n; i++){
        while (st.size() >= 2){
            if (is_clockwise(st[st.size() - 2], st[st.size() - 1], ind[i]))
                st.pop_back();
            else
                break;
        }
        st.push_back(ind[i]);
    }
    int l = 0, r = st.size() - 1;
    while (r - l + 1 > 3){
        if (is_clockwise(st[r], st[l], st[l + 1])){
            l++;
            continue;
        }
        if (is_clockwise(st[r - 1], st[r], st[l])){
            r--;
            continue;
        }
        break;
    }
    give_answer(r - l + 1);
    return 0;
}

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