이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "trilib.h"
#define long long long
using namespace std;
int n;
vector<int> up, down, up_hull, down_hull, ans;
int main() {
n = get_n();
for(int i = 3; i <= n; i++) {
if(is_clockwise(1, 2, i)) down.push_back(i);
else up.push_back(i);
}
up.push_back(2);
down.push_back(2);
sort(up.begin(), up.end(), [] (int j, int k) { return is_clockwise(1, j, k); });
sort(down.begin(), down.end(), [] (int j, int k) { return !is_clockwise(1, j, k); });
if(up.size() > 1) {
up_hull.push_back(1);
up_hull.push_back(up[0]);
for(int i = 1; i < up.size(); i++) {
while(up_hull.size() >= 2 && !is_clockwise(up_hull[up_hull.size()-2], up_hull[up_hull.size()-1], up[i]))
up_hull.pop_back();
up_hull.push_back(up[i]);
}
}
if(down.size() > 1) {
down_hull.push_back(1);
down_hull.push_back(down[0]);
for(int i = 1; i < down.size(); i++) {
while(down_hull.size() >= 2 && is_clockwise(down_hull[down_hull.size()-2], down_hull[down_hull.size()-1], down[i]))
down_hull.pop_back();
down_hull.push_back(down[i]);
}
}
if(down_hull[0] == 1 && up_hull[0] == 1) down_hull.erase(down_hull.begin());
if(down_hull.back() == 2 && up_hull.back() == 2) down_hull.pop_back();
reverse(down_hull.begin(), down_hull.end());
vector<int> res = up_hull;
for(int i: down_hull) res.push_back(i);
ans.push_back(res[0]);
ans.push_back(res[1]);
for(int i = 2; i < res.size(); i++) {
while(ans.size() >= 2 && !is_clockwise(ans[ans.size()-2], ans[ans.size()-1], res[i]))
ans.pop_back();
ans.push_back(res[i]);
}
/* for(int i: up) cout << i << ' '; */
/* cout << endl; */
/* for(int i: down) cout << i << ' '; */
/* cout << endl; */
/* for(int i: up_hull) cout << i << ' '; */
/* cout << endl; */
/* for(int i: down_hull) cout << i << ' '; */
/* cout << endl; */
/* for(int i: ans) cout << i << ' '; */
/* cout << endl; */
cout << ans.size() << endl;
}
컴파일 시 표준 에러 (stderr) 메시지
tri.cpp: In function 'int main()':
tri.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < up.size(); i++) {
~~^~~~~~~~~~~
tri.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < down.size(); i++) {
~~^~~~~~~~~~~~~
tri.cpp:45:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 2; i < res.size(); i++) {
~~^~~~~~~~~~~~
# | 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... |