제출 #229813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229813		dolphingarlic	Triangles (CEOI18_tri)	C++14	0 / 100	5 ms	384 KiB

tri

#include "trilib.h"

#include <bits/stdc++.h>
using namespace std;

deque<int> c_hull(deque<int> points) {
    if (points.size() < 4) {
        if (points.size() == 3 && is_clockwise(points[2], points[1], points[0]))
            reverse(points.begin(), points.end());
        return points;
    }

    random_shuffle(points.begin(), points.end());
    deque<int> left, right;
    for (int i = 2; i < points.size(); i++) {
        if (is_clockwise(points[0], points[1], points[i])) right.push_back(points[i]);
        else left.push_back(points[i]);
    }
    if (left.size() < right.size()) left.push_back(points[0]);
    else right.push_back(points[0]);
    if (left.size() < right.size()) left.push_back(points[1]);
    else right.push_back(points[1]);

    deque<int> l_hull = c_hull(left), r_hull = c_hull(right);
    while (!is_clockwise(l_hull[l_hull.size() - 2], l_hull.back(), r_hull[0])) {
        l_hull.push_front(l_hull.back());
        l_hull.pop_back();
    }
    for (int i : r_hull) {
        while (l_hull.size() > 1 && !is_clockwise(l_hull[l_hull.size() - 2], l_hull.back(), i))
            l_hull.pop_back();
        l_hull.push_back(i);
    }
    while (l_hull.size() > 2) {
        while (l_hull.size() > 2 && !is_clockwise(l_hull.back(), l_hull[0], l_hull[1]))
            l_hull.pop_front();
        if (l_hull.size() > 2 && is_clockwise(l_hull[l_hull.size() - 2], l_hull.back(), l_hull[0]))
            break;
        else l_hull.pop_back();
    }
    return l_hull;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n = get_n();
    deque<int> points(n);
    iota(points.begin(), points.end(), 1);
    give_answer(c_hull(points).size());
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

tri.cpp: In function 'std::deque<int> c_hull(std::deque<int>)':
tri.cpp:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 2; i < points.size(); i++) {
                     ~~^~~~~~~~~~~~~~~

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