Submission #1321282

#TimeUsernameProblemLanguageResultExecution timeMemory
1321282LudisseyTriangles (CEOI18_tri)C++20
0 / 100
1 ms332 KiB
#include <bits/stdc++.h>
#include "trilib.h"
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n=get_n();
    int root=1;
    int x1,x2;
    vector<int> a;
    vector<int> b;
    a.push_back(2);
    b.push_back(2);
    for (int i = 3; i <= n; i++)
    {
        if(i==root) continue;
        if(is_clockwise(1,2,i)) a.push_back(i);
        else b.push_back(i);
    }
    sort(all(a), [root](int _a, int _b){ return is_clockwise(root,_a,_b); });
    sort(all(b), [root](int _a, int _b){ return !is_clockwise(root,_a,_b); });
    vector<int> convA;
    convA.push_back(root);
    convA.push_back(a[0]);
    for (int i = 1; i < sz(a); i++)
    {
        while(true){
            x2=convA.back();
            convA.pop_back();
            x1=convA.back();
            if(is_clockwise(x1,x2,a[i])){
                convA.push_back(x2);
                break;
            }
        }
        convA.push_back(a[i]);
    }

    reverse(all(convA));
    convA.pop_back();
    reverse(all(convA));
    convA.push_back(root);

    vector<int> convB;
    convB.push_back(root);
    convB.push_back(b[0]);
    for (int i = 1; i < sz(b); i++)
    {
        while(true){
            x2=convB.back();
            convB.pop_back();
            x1=convB.back();
            if(!is_clockwise(x1,x2,b[i])){
                convB.push_back(x2);
                break;
            }
        }
        convB.push_back(b[i]);
    }
    reverse(all(convB));
    convB.pop_back();
    reverse(all(convB));
    convB.push_back(root);
    reverse(all(convB));


    vector<int> convAB,conv;
    for (int i = 1; i < sz(convA); i++)
    {
        if(sz(convAB)>0&&convAB.back()==convA[i]) continue;
        convAB.push_back(convA[i]);
    }
    for (int i = 1; i < sz(convB); i++)
    {
        if(sz(convAB)>0&&convAB.back()==convB[i]) continue;
        convAB.push_back(convB[i]);
    }
    int sAB=sz(convAB);
    for (int i = 0; i < sAB; i++)
    {
        convAB.push_back(convAB[i]);
    }
    conv.push_back(convAB[0]);
    conv.push_back(convAB[1]);
    for (int i = 2; i < sz(convAB); i++)
    {
        while(true){
            x2=conv.back();
            conv.pop_back();
            x1=conv.back();
            if(is_clockwise(x1,x2,convAB[i])){
                conv.push_back(x2);
                break;
            }
        }
        conv.push_back(convAB[i]);
    }
    vector<int> cnt(n+1);
    int sm=0;
    for (int i = 0; i < sz(conv); i++)
    {
        cnt[conv[i]]++;
        if(cnt[conv[i]]==2) sm++;
    }
    
    give_answer(sm);
    return 0;
}   
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...