Submission #972475

#	Time	Username	Problem	Language	Result	Execution time	Memory
972475		Charizard2021	Triangles (CEOI18_tri)	C++17	100 / 100	32 ms	4092 KiB

tri

#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;
vector<int> orderDivide(vector<int> points){
    if((int)points.size() <= 1){
        return points;
    }
    int cur = points[rand() % (int)points.size()];
    vector<int> leftHalf;
    vector<int> rightHalf;
    for(int i = 0; i < (int)points.size(); i++){
        if(points[i] != cur){
            if(is_clockwise(1, cur, points[i])){
                rightHalf.push_back(points[i]);
            }
            else{
                leftHalf.push_back(points[i]);
            }
        }
    }
    vector<int> leftorderDivide = orderDivide(leftHalf);
    vector<int> rightorderDivide = orderDivide(rightHalf);
    leftorderDivide.push_back(cur);
    for(int a : rightorderDivide){
        leftorderDivide.push_back(a);
    }
    return leftorderDivide;
}
int main(){
    srand((unsigned) time(NULL));
    int n = get_n();
    vector<int> points;
    for(int i = 2; i <= n; i++){
        points.push_back(i);
    }
    points = orderDivide(points);
    points.insert(points.begin(), 1);
    vector<int> cur;
    cur.push_back(1);
    for(int i = 1; i < (int)points.size(); i++){
        while((int)cur.size() >= 2 && !is_clockwise(cur[(int)cur.size() - 2], cur.back(), points[i])){
            cur.pop_back();
        }
        cur.push_back(points[i]);
    }
    points = cur;
    deque<int> dq;
    for(int i = 0; i < (int)points.size(); i++){
        dq.push_back(points[i]);
    }
    while(true){
        bool works = true;
        int cur = dq.back();
        dq.pop_back();
        if(is_clockwise(dq.back(), cur, dq.front())){
            dq.push_back(cur);
        }
        else{
            works = false;
        }
        cur = dq.front();
        dq.pop_front();
        if(is_clockwise(dq.back(), cur, dq.front())){
            dq.push_front(cur);
        }
        else{
            works = false;
        }
        if(works){
            break;
        }
    }
    give_answer(dq.size());
}

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