Submission #872932

#	Time	Username	Problem	Language	Result	Execution time	Memory
872932		Darren0724	Triangles (CEOI18_tri)	C++17	20 / 100	1 ms	600 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
//#include "trilib.c"
using namespace std;


int32_t main() {
    int n=get_n();
    int cnt=0;
    int ans=0;
    int i=1;
    int mn=-1;
    int mx=-1;
    int st=-1;
    for(int j=2;j<=n;j++){
        if(st==-1){
            st=j;
            mn=mx=j;
            continue;
        }
        int t=is_clockwise(i,st,j);
        if(t){
            if(mx==-1||is_clockwise(i,mx,j)){
                mx=j;
            }
        }
        else{
            if(mn==-1||!is_clockwise(i,mn,j)){
                mn=j;
            }
        }
    }
    assert(mn!=-1);
    vector<int> pt;
    for(int i=1;i<=n;i++){
        if(i==mn){
            continue;
        }
        pt.push_back(i);
    }
    sort(pt.begin(),pt.end(),[&](int a,int b){return is_clockwise(mn,b,a);});
    vector<int> s;
    s.push_back(mn);
    for(int i:pt){
        while(s.size()>1&&is_clockwise(s.end()[-2],s.end()[-1],i)){
            s.pop_back();
        }
        s.push_back(i);
    }
    give_answer(s.size());

    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'int32_t main()':
tri.cpp:9:9: warning: unused variable 'cnt' [-Wunused-variable]
    9 |     int cnt=0;
      |         ^~~
tri.cpp:10:9: warning: unused variable 'ans' [-Wunused-variable]
   10 |     int ans=0;
      |         ^~~

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