제출 #96421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96421		easrui	Triangles (CEOI18_tri)	C++14	100 / 100	42 ms	2296 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;
const int MN = 4e4+5;
vector<int> U,D;
int stD[MN],stU[MN],cntD,cntU,s,e,ans;
bool isend;
bool cmp1(int a, int b)
{
    return is_clockwise(1,a,b);
}

bool cmp2(int a, int b)
{
    return is_clockwise(2,a,b);
}

int main()
{
    int N = get_n();
    for(int i=3; i<=N; i++){
        if(is_clockwise(1,2,i)) D.push_back(i);
        else U.push_back(i);
    }
    sort(D.begin(),D.end(),cmp1);
    sort(U.begin(),U.end(),cmp2);
    stD[0] = 1;
    stD[1] = 2;
    cntD = 1;
    for(int x : D){
        while(cntD && !is_clockwise(stD[cntD-1],stD[cntD],x)) cntD--;
        stD[++cntD] = x;
    }
    //if(D.size()) while(!is_clockwise(stD[cntD-1],stD[cntD],1)) cntD--;
    stU[0] = 2;
    stU[1] = 1;
    cntU = 1;
    for(int x : U){
        while(cntU && !is_clockwise(stU[cntU-1],stU[cntU],x)) cntU--;
        stU[++cntU] = x;
    }
    //if(U.size()) while(!is_clockwise(stU[cntU-1],stU[cntU],2)) cntU--;
    ans = cntD+cntU;
    if(!D.size() || !U.size()){
        give_answer(ans);
        return 0;
    }
    if(!is_clockwise(stD[cntD],stU[1],stU[2])){
        s = cntD, e = 2;
        isend = false;
        while(!isend){
            isend = true;
            if(s && !is_clockwise(stD[s-1],stD[s],stU[e])){
                s--;
                isend = false;
            }
            if(e<cntU && !is_clockwise(stD[s],stU[e],stU[e+1])){
                e++;
                isend = false;
            }
        }
        ans -= (cntD-s) + (e-1);
    }
    if(!is_clockwise(stU[cntU],stD[1],stD[2])){
        s = cntU, e = 2;
        isend = false;
        while(!isend){
            isend = true;
            if(s && !is_clockwise(stU[s-1],stU[s],stD[e])){
                s--;
                isend = false;
            }
            if(e<cntD && !is_clockwise(stU[s],stD[e],stD[e+1])){
                e++;
                isend = false;
            }
        }
        ans -= (cntU-s) + (e-1);
    }
    give_answer(ans);
}

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