Submission #518890

#	Time	Username	Problem	Language	Result	Execution time	Memory
518890		ETK	Triangles (CEOI18_tri)	C++14	100 / 100	117 ms	1988 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;
#define chk is_clockwise
int main(){
    int n = get_n();
    vector <int> p;
#define pre(x) ((x + p.size() - 1) % p.size())
#define nxt(x) ((x + 1) % p.size())
    if(chk(1,2,3))p = {1,2,3};
    else p = {1,3,2};
    for(int i = 4;i <= n;i++){
        int L = 1,R = p.size() - 2,l = -1;
        while(L < R){
            int mid = (L + R) >> 1;
            if(chk(p[0],p[mid+1],i))L = mid+1;
            else R = mid;
        }
        if(!chk(p[0],p[L],i))l = 0;
        else if(!chk(p[L],p[L+1],i))l = L;
        else if(!chk(p[L+1],p[0],i))l = L+1;
        if(l == -1)continue;//在凸包内
        int r = nxt(l);
        //找到凸包中前后需要删除的点
        while(!chk(p[pre(l)],p[l],i))l = pre(l);
        while(!chk(i,p[r],p[nxt(r)]))r = nxt(r);
        if(nxt(l) <= r){
            if(nxt(l) != r){
                int t = nxt(l);
                p.erase(p.begin() + nxt(l),p.begin() + r);
                r = t;
            }
            p.insert(p.begin() + r,i);
        }else{
            p.erase(p.begin() + nxt(l),p.end());
            if(r)p.erase(p.begin(),p.begin() + r);
            p.push_back(i);
        }
    }
    give_answer(p.size());
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:27:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |         if(nxt(l) <= r){
      |                   ^
tri.cpp:28:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |             if(nxt(l) != r){
      |                       ^

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