Submission #321201

#TimeUsernameProblemLanguageResultExecution timeMemory
321201phathnvTriangles (CEOI18_tri)C++11
0 / 100
1 ms384 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;
            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...