Submission #532653

#	Time	Username	Problem	Language	Result	Execution time	Memory
532653		AugustinasJucas	Triangles (CEOI18_tri)	C++14	100 / 100	26 ms	2872 KiB

tri

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

using namespace std;
int n;
int pirmas = 0;
/*
int get_n(){
    return 6;
}
int queries = 0;
vector<int> x(40), y(40);
int is_clockwise(int a, int b, int c) {
	assert(a >= 1 && a <= n);
	assert(b >= 1 && b <= n);
	assert(c >= 1 && c <= n);
	assert(a!=b && a!=c && b!=c);
	queries++;
        if(queries == 1000 * 1000 + 1)
            printf("Too many queries!");
	return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a]) < 0;
}
*/
/*
bool is_clockwise (int a, int b, int c) {
    cout << "ar " << a << " -> " << b << " -> " << c << " pagal? ";
    bool ans;
    cin >> ans;
    return ans;
}*/
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();
/*    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x[i];
        cin >> y[i];
    }*/
}
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());
/*
    cout << "jei " << A << "; " << B << " skelia per puse, tai hullai: \n";
    cout << "virsuje: ";
    for(auto x : uphul) cout << x << " ";
    cout << endl << "apacioje: ";
    for(auto x : downhul) cout << x << " ";
    cout << endl << endl;
    cout << "bendras isrikiuotas: "; 
    for(auto x : fin) {
        cout << x << " ";
    }
    cout << endl << "finalinis: ";
    for(auto x : finhul) {
        cout << x << " ";
    }
    */
    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'std::vector<int> pasalink(std::vector<int>)':
tri.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 1; i < mas.size(); i++){
      |                    ~~^~~~~~~~~~~~
tri.cpp: In function 'std::vector<int> pasalink1(std::vector<int>)':
tri.cpp:52:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i = 0; i < mas.size(); i++){
      |                        ~~^~~~~~~~~~~~
tri.cpp: In function 'int main()':
tri.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < uphul.size()-1; i++) {
      |                    ~~^~~~~~~~~~~~~~~~
tri.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     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