이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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() - 1,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());
}
컴파일 시 표준 에러 (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){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |