Submission #321202

#TimeUsernameProblemLanguageResultExecution timeMemory
321202phathnvTriangles (CEOI18_tri)C++11
100 / 100
31 ms2660 KiB
#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;
}
#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...