Submission #954944

#	Time	Username	Problem	Language	Result	Execution time	Memory
954944		ThegeekKnight16	Triangles (CEOI18_tri)	C++17	20 / 100	1 ms	600 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);}
    }

    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 -= (i == 0 ? 1 : 2);}
    }

    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:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < hull.size(); i++)
      |                     ~~^~~~~~~~~~~~~

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