Submission #954949

#	Time	Username	Problem	Language	Result	Execution time	Memory
954949		ThegeekKnight16	Triangles (CEOI18_tri)	C++17	100 / 100	65 ms	2200 KiB

tri

#include <bits/stdc++.h>
using namespace std;
#include "trilib.h"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void ordena(vector<int> &v)
{
    if (v.size() <= 1) return;
    vector<int> l, r;
    for (int i = 1; i < v.size(); i++)
    {
        // cerr << "||1 " << v[0] << " " << v[i] << '\n';
        if (is_clockwise(1, v[0], v[i])) l.push_back(v[i]);
        else r.push_back(v[i]);
    }
    ordena(l); ordena(r);
    l.push_back(v[0]);
    v = l;
    for (auto x : r) v.push_back(x);
}

int main()
{
    int N = get_n();
    vector<int> points(N-1);
    iota(points.begin(), points.end(), 2);
    shuffle(points.begin(), points.end(), rng);
    ordena(points);
    vector<int> hull; bool putOne = 0;
    for (int i = 0; i < N-1; i++)
    {
        hull.push_back(points[i]);
        // cerr << "i: " << i << "||1 " << points[i] << " " << points[(i+1)%(N-1)] << '\n';
        if (!putOne && is_clockwise(1, points[i], points[(i+1)%(N-1)])) {putOne = 1; hull.push_back(1);}
    }

    bool removedSome = 1;
    for (int t = 0; t <= N && removedSome; t++)
    {
        removedSome = 0;
        for (int i = 0; i < hull.size(); i++)
        {
            int tam = hull.size();
            int ant = hull[(i+tam-1)%tam];
            int prox = hull[(i+1)%tam];
            if (!is_clockwise(hull[i], ant, prox)) {hull.erase(hull.begin()+i); --i; removedSome = 1;}
        }
    }

    give_answer((int)hull.size());
}

Compilation message (stderr)

tri.cpp: In function 'void ordena(std::vector<int>&)':
tri.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 1; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
tri.cpp: In function 'int main()':
tri.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i < hull.size(); i++)
      |                         ~~^~~~~~~~~~~~~

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