제출 #321185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
321185		phathnv	Triangles (CEOI18_tri)	C++11	75 / 100	32 ms	1900 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];
 
int main(){
    _n = get_n();
    int tmp = 2;
    for(int i = 3; i <= _n; i++)
        if (is_clockwise(1, tmp, i))
            tmp = i;
    bool flag = 0;
    for(int i = 2; i <= _n; i++){
        if (tmp == i)
            continue;
        if (is_clockwise(1, tmp, i)){
            flag = 1;
            break;
        }
    }
    if (flag == 0){ /// 1 in convex hull
        for(int i = 1; i <= _n; i++)
            ind[i] = i;
        sort(ind + 2, ind + 1 + _n, [](const int &a, const int &b){
                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]);
        }
        give_answer(st.size());
    } else {
        for(int i = 1; i <= _n; i++)
            ind[i] = i;
        sort(ind + 3, ind + 1 + _n, [](const int &a, const int &b){
                bool tA = is_clockwise(1, 2, a);
                bool tB = is_clockwise(1, 2, b);
                if (tA != tB)
                    return tB;
                return (!is_clockwise(1, a, b));
             });
        vector <int> st;
        st.push_back(2);
        for(int i = 3; 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: 0 / 25