Submission #532654

#	Time	Username	Problem	Language	Result	Execution time	Memory
532654		AugustinasJucas	Triangles (CEOI18_tri)	C++14	100 / 100	25 ms	2852 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"

using namespace std;
int n;
int pirmas = 0;
bool les(int &a, int &b) {  // ar a < b
    if(a == pirmas) return true;
    if(b == pirmas) return false;
    return is_clockwise(pirmas, a, b);
}
vector<int> pasalink(vector<int> mas){
    vector<int> ret = {mas[0]};
    for(int i = 1; i < mas.size(); i++){
        int k = ret.back();
        int d = mas[(i+1)%mas.size()];
        bool cl = is_clockwise(k, mas[i], d);
        if(cl){
            ret.push_back(mas[i]);
        }
    }
    return ret;
}
vector<int> pasalink1(vector<int> mas){
    vector<int> ret = {};
    while(true) {
        bool don = 0;
        for(int i = 0; i < mas.size(); i++){
            int k = mas[(i-1+mas.size())%mas.size()];
            int d = mas[(i+1)%mas.size()];
            bool cl = is_clockwise(k, mas[i], d);
            if(cl){
                ret.push_back(mas[i]);
            }else {
                don = 1;
            }
        }
        mas = ret;
        ret.clear();
        if(!don) break;
    }
    return mas;
}
vector<int> hullink(vector<int> &mas) {
    pirmas = mas[0];
    sort(mas.begin(), mas.end(), les);
    if(mas.size() == 2) {
        return mas;
    }
    return pasalink(mas);
}
void nuskaityk(){
    n = get_n();
}
int main () {
    srand(time(0));
    
    nuskaityk();
    int A = 1;
    int B = 2;
    
    vector<int> up = {A, B}, down = {A, B};

    for(int i = 3; i <= n; i++) {
        bool cl = is_clockwise(A, B, i);
        if(cl) up.push_back(i);
        else down.push_back(i);
    }
    
    auto uphul = hullink(up);
    auto downhul = hullink(down);
        
    if(uphul[1] == B){
        swap(uphul, downhul);
    }
    
    vector<int> fin;
    for(int i = 0; i < uphul.size()-1; i++) {
        fin.push_back(uphul[i]);
    }
    for(int i = 1; i < downhul.size(); i++) {
        fin.push_back(downhul[i]);
    }
    auto finhul = pasalink1(fin);
    give_answer(finhul.size());
    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'std::vector<int> pasalink(std::vector<int>)':
tri.cpp:14:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i = 1; i < mas.size(); i++){
      |                    ~~^~~~~~~~~~~~
tri.cpp: In function 'std::vector<int> pasalink1(std::vector<int>)':
tri.cpp:28:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i = 0; i < mas.size(); i++){
      |                        ~~^~~~~~~~~~~~
tri.cpp: In function 'int main()':
tri.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i = 0; i < uphul.size()-1; i++) {
      |                    ~~^~~~~~~~~~~~~~~~
tri.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 1; i < downhul.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~

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